Selection Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Selection Sort.

Selection sort is a simple, quadratic (O(n2)) in-place comparison sort algorithm that divides the array into two lists: an already sorted part and a to-sort part. The algorithm moves for through the array and inserts the next value in-place by searching the unsorted part of the array for the next value. In practice, the selection sort is useful when memory is limited.

How do it…

Here is a simple selection sort algorithm in JavaScript:

function selectionSort(a) {
  for (var i, iMin, j = 0, n = a.length, oTemp; j < n-1; j++) {
    iMin = j;

    for (i = j+1; i < n; i++) {
      if (a[i] < a[iMin]) {
        iMin = i;
      }
    }

    if (iMin !== j) {
      oTemp = a[iMin];
      a[iMin] = a[j];
      a[j] = oTemp;
    }
  }
}

Here it is in action:


Restart Selection Sort With a New Array

If we take a 10,000 element array and sort it, here is how selection sort compares to native array sort (prints to the console):

Selection Sort Comparison Tests

Here is the bingo selection sort algorithm variant in JavaScript, which is faster for sorting arrays with duplicate values:

function bingoSort(a) {
  for (var i, iMin, j = 0, n = a.length, oTemp; j < n-1; j++) {
    iMin = j;

    for (i = j+1; i < n; i++) {
      if (a[i] < a[iMin]) {
        iMin = i;
      }
    }

    if (iMin !== j) {
      oTemp = a[iMin];
      a[iMin] = a[j];
      a[j] = oTemp;
    }
  }
}

Here we compare 10,000 element array, sorting it with bingo sort versus selection sort. The array has a values 1 - 5,000 duplicated once each, so bingo sort should perform half as many searches (prints to the console):

Bingo Sort Comparison Tests

How it works…

The selection sort algorithm moves forward through the array, starting at index n=0. It searches the remaining unsorted values (n to end of array) for the next smallest value and swaps it with the value at n. Then the index is incremented and the process repeats, until the length-2 index is reached (we know at length-2 that the value length-1 is the maximum value, because it is greater than the value at length-2).

There is no performance boost, if the array is already sorted, or if there are multiples of the same value. Of the quadratic sorting algorithm, selection sort usually outperforms Bubble Sort, because the inner loop usually visits less nodes, but because it visits all remaining nodes searching for the next highest value, it tends to make about twice as many comparisons as Insertion Sort. If you run the comparison test, you will see that selection sort is 10-20x slower when sorting a 10,000 value array than the native sorting algorithm.

There is a common variant known as bingo sort, which can provide a significant performance boost, when an array contains multiple of the same value. The algorithm works, by keeping track of all indices containing the next highest value (instead of just one), and swapping them all each pass. It offers no benefit, if you do not expect duplicate values in an array.

There’s more…

For more information, see the Insertion Sort Wikipedia article.