The Efficiency of Selection Sort

Selection Sort contains two types of steps: comparisons and swaps. We compare each value with the lowest number we’ve encountered in each pass-through, and we swap the lowest number into its correct position.

Looking back at our example array that contains five elements, we had to make a total of 10 comparisons. Let’s break it down in the following table:

That’s a grand total of 4 + 3 + 2 + 1 = 10 comparisons.

To put it in a way that works for arrays of all sizes, we’d say that for N elements, we make

(N - 1) + (N - 2) + (N - 3) … + 1 comparisons.

As for swaps, though, we only need to make a maximum of one swap per pass-through. This is because in each pass-through, we make either one or zero swaps, depending on whether the lowest number of that pass-through is already in the correct position. Contrast this with Bubble Sort, where in a worst-case scenario we have to make a swap for each and every comparison.

Here’s a side-by-side comparison of Bubble Sort and Selection Sort:

From this comparison, it’s clear Selection Sort takes about half the number of steps Bubble Sort does, indicating that Selection Sort is twice as fast.