Selection sort is similar in complexity to insertion sort but almost always performs worse. This is due to the fact that selection sort has an exact number of comparisons based on n, which can be defined using the arithmetic progression:

This makes its best case always contain the same amount of comparisons as its worst.

While selection sort is faster than most O(\log n) sorts for small lists, insertion sort is normally the preferable choice. It’s main favourable property is that it will perform at most n - 1 element swaps, so it may be useful if swapping is expensive.

Complexity

Time			Space
Worst case	Best case	Average case	Worst case
O(n^2)	O(n^2)	O(n^2)	O(1) auxiliary

Comparing to heapsort

Heapsort uses the exact same technique that selection sort does in finding the minimum element and then ‘detaching’ the first element from the list and sorting the remainder. The only difference between them is that instead of searching for the minimum element every iteration, heapsort utilises the heap data structure to organise the sub-list and guarentee O(n \log n) run time.

Visualisation

Use the controls to playback selection sort on the data set.

See the Sorting Visualiser page for more visualisations.

Code

public class SelectionSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        for (int i = 0; i < list.Count - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < list.Count; j++) {
                if (list[j].CompareTo(list[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                Swap(list, i, minIndex);
            }
        }
    }

    private void Swap(IList<T> list, int a, int b)
    {
        T temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}

public class SelectionSort {
    public static void sort(Integer[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(array, i, minIndex);
            }
        }
    }

    private static void swap(Integer[] array, int a, int b) {
        Integer temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

/**
 * Sorts an array using selection sort.
 * @param {Array} array The array to sort.
 * @param {function} compare The compare function.
 * @param {function} swap A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function sort(array, compare, swap) {
  for (var i = 0; i < array.length - 1; i++) {
    var minIndex = i;

    for (var j = i + 1; j < array.length; j++) {
      if (compare(array, j, minIndex) < 0) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      swap(array, i, minIndex);
    }
  }

  return array;
}

def default_compare(a, b):
  if a < b:
    return -1
  elif a > b:
    return 1
  return 0

def sort(array, compare=default_compare):
  for i in range(0, len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
      if compare(array[j], array[min_index]) < 0:
        min_index = j
    if min_index != i:
      array[i], array[min_index] = array[min_index], array[i]
  return array

module SelectionSort
  # Sorts an array using selection sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    (0..array.length - 1).each do |i|
      minIndex = i
      (i + 1..array.length - 1).each do |j|
        if compare.call(array[j], array[minIndex]) < 0
          minIndex = j
        end
      end
      if minIndex != i
        array[i], array[minIndex] = array[minIndex], array[i]
      end
    end
  end
end

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

More posts tagged Sorting