Selection Sort

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Properties

• Not stable
• O(1) extra space
• Θ(n²) comparisons
• Θ(n) swaps
• Not adaptive

Discussion

From the comparions presented here, one might conclude that selection sort should never be used. It does not adapt to the data in any way (notice that the four animations above run in lock step), so its runtime is always quadratic.

However, selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

Directions

• Click on above to restart the animations in a row, a column, or the entire table.
• Click directly on an animation image to start or restart it.
• Click on a problem size number to reset all animations.

Key

• Black values are sorted.
• Gray values are unsorted.
• A red triangle marks the algorithm position.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

Quicksort is Optimal by Robert Sedgewick and Jon Bentley, Knuthfest, Stanford University, January, 2002.