Growing with the Web

Selection sort

Published , updated
Tags:

Selection sort is an O(n^2) sorting algorithm that works by searching through a list to find the minimum element and swapping it for the first in the list. After every swap, selection sort is performed on the list with the head removed (ie. the minimum element). Due to the way that elements are swapped anywhere in the list, this is not a stable sort.

Selection sort example

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:

(n - 1) + (n - 2) + ... + 2 + 1 = n(n - 1) / 2

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

Comments

comments powered by Disqus
Like this article?
Subscribe for more!