Selection Sort: Taking the Smallest of What Remains

Selection sort orders an array by scanning the unsorted part for its smallest item and swapping that item to the front of the unsorted part, so the sorted part grows from the left by one item per pass. This card traces it, counts its comparisons, and shows why it is not stable.

Pass i starts with min at index i and walks the rest of the array, moving min to any item smaller than the one it marks. When the scan ends, min marks the smallest unsorted item, and one swap moves it to index i. If it is already there, nothing moves. The trace sorts 6 2 9 4 1 7 3, with i on the place being filled and min on where the smallest item was found.

The array was sorted after pass 3, and the sort went on scanning anyway. It has no way to stop early: the smallest item is known only once every unsorted item has been looked at. Pass 1 compares 6 times, pass 2 compares 5 times, and so on down to 1, so the total is n(n − 1)/2 comparisons on every input of n items, 21 for seven. The swaps are another matter. There is at most one per pass, so at most n − 1 in all, and this run needed two.

That swap is also why selection sort is not stable. It moves the item at the front of the unsorted part to wherever the minimum was found, which can be far to the right, jumping over every item in between. If one of those items has the same key as the item jumping, the two change order, and the sort has broken the order equal items arrived in. Bubble sort and insertion sort never move an item past an equal one, which is the difference.

The costs, for an array of n items, are these.

Selection sort's time is fixed by n alone, so it is never faster on easier input. Its one strength is the swap count: when writing an item somewhere costs far more than comparing two, as with large records copied by value, n − 1 swaps can matter more than n²/2 comparisons.