Selection sort
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 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.