Selection Sort

By Victor Arce

Selection sort keeps the list split into two parts: a sorted region at the front and an unsorted region after it. Each pass scans the unsorted part for the smallest remaining value and moves it to the front of that region. The sorted part grows from the left, one element per pass.

Step through it below — the comparisons scan for the minimum, then a single swap drops it into place.

How it works

For each position from left to right, we look at every value still unsorted and remember the smallest one we have seen. After scanning the whole unsorted part, we swap that smallest value into the current position. Because each pass places exactly one value in its final spot, an array of n items takes n − 1 passes.

Notice it makes few swaps (at most one per pass) but many comparisons — the opposite balance to bubble sort.

Cost

Selection sort always does on the order of n² comparisons — best, average, and worst case alike (it has no early exit). It is in-placeIn-place: sorts within the original array using only a little extra memory (no second array). (O(1) extra memory) but not stableStable: equal values keep their original relative order after sorting., since the long-distance swap can reorder equal values. Its predictable, minimal-swap behaviour makes it useful when writes are expensive.

Back to Sorting Algorithms