Selection Sort

Previously we looked at bubble sort algorithm which has O(n^2) quadratic time regardless of order of original collection. The problem with bubble sort is compounded by the number of swaps it has to do within each pass. Everytime the algorithm encounters a unordered comparison, it does a swap which is costly. To avoid that we have selection sort which produces considerably less swaps.

Selection sort works by performing a number of passes identical to bubble sort however the difference is how the inner loop works. Unlike bubble sort, selection sort does not perform a swap every time it encounters two unordered comparisons. Index of largest element is sought. Once obtained and at the conclusion of the inner loop, the last element of the array is swapped with this largest element. The problem domain is then reduced by one since after the first pass the largest value is now in its sorted position. The cycle repeats up to the final pass. Obvious advantage is less data swapping compared to Bubble sort but worst case running time is still O(n^2). Best case is also O(n^2) since every element is scanned per pass.

Here is the sequence of events for selection sort.
Initial: 6 1 3 2 7 5 4
6 1 3 2 4 5 7 //Largest element: 7 at index 4. Swap with end element, 4.
5 1 3 2 4 6 7 //Largest element: 6 at index 0. Swap with end element, 5.
4 1 3 2 5 6 7 //Largest element: 5 at index 0. Swap with end element, 4.
2 1 3 4 5 6 7 //Largest element: 4 at index 0. Swap with end element, 2. 
2 1 3 4 5 6 7 //Largest element: 3 at index 2. No change last element == end element.
1 2 3 4 5 6 7 //Largest element: 2 at index 0. Swap with end element, 1.  
Done.

Like bubble sort, selection sort algorithm is also an in-place algorithm. What this means is that it uses little extra memory to complete its sorting operation. The source code for selection sort:

public int SelectionSort(ref int[] array)
{
  int swapcount = 0;
  for (int i = array.Length-1; i >= 0; i-- )
  {
    int index = 0;
    for (int j = 0; j <= i; j++)
    {
      if (array[j] >= array[index]) index = j;
    }
    if (index != i)
    {
      Swap(ref array, i, index);
      swapcount++;
    }
  }
  return swapcount;
}

How does the above code work:
The first loop is the number of passes and runs from 0 - n as index 'i'. The innerloop also runs from 0-n however in this instant n = i. The inner loop compares the item at stored index with item currently being looked at. If item of stored index is smaller then index is updated. Once the inner loop terminates for current pass, a swap is made if index of largest items is not the same as index of final element. Every time a swap is made a count is kept and this is returned at the conclusion of the algorithm.

Next: Insertion Sort.
Previous: Bubble Sort.
Landing page: Part One.