Elementary Sorting Algorithms – Selection Sort

It is a simple sorting algorithm, the logic behind it as follows:

  1. Start with element at index (i) => i = 0
  2. Find the smallest element on the right of an element at index (i)
  3. Swap the two elements
  4. Increment the index, move to the right
  5. Repeat untill the end

The Invariants

  1. Elements to the left of the index are never changed, they are in ascending order
  2. No element to the right of the index is smaller than any element to the left of it

Sample Code

for(int i=0;i<array.length()){
    int min = i;
    for(int j=i+1;j<array.length()){
       if (less(arr[j],arr[min])){
           min = j;
       };
    }
    swap(arr[i],arr[min]);
}

Mathematical Analysis

  1. Proposition: Selection sort uses N^2/2 compares and N exchanges
  2. Selection sort runs in quadratic time, even if input is sorted
  3. Data movement is minimal - Linear number of exchanges
0