Selection Sort

Selection Sort Process

Imagine that you have a deck of 10 numbered cards that are in a random order, and that you are only allowed to have 2 cards facing up at a time. How would you sort them?

A nice organizational approach would be to create 2 piles: a sorted pile and an unsorted pile. The idea of a sorted pile would be that we never need to compare values inside of it, just add cards to the pile without looking. Obviously, the sorted pile would start out empty, so how would we fill it properly?

Well, if you could choose a card to go into the sorted pile, what would it be?

Odds are, the smallest value is the most helpful. To find the smallest card, we could flip over the first card in the unsorted pile, and begin comparing it to the rest of the pile.

If we come across a card that is smaller than our current smallest, we can then flip over our previous smallest and now "keep" our new smallest. So in this case, we'd see that 2 is smaller than 5, so 2 becomes our new smallest value as we continue.

Once we've reached the end of the pile, we know that our card face-up is the smallest value in the pile. For this example, the smallest value would be 1.

We can then take this card and place it into our sorted pile.

The next card that we'd like in that pile would presumably be the next smallest value. To find that, we can simply repeat the process we've already done to find the smallest card, then we just place that at the back of our sorted pile. In this case, we'd find 2 to be the next smallest value:

We can then continue this process until all of our cards are in the sorted pile. This algorithm is known as Selection Sort.

Selection Sort Visualization

You can find the next value to add to the sorted list by pressing the Step button, undo the last value sorted by pressing the Step Back button, or continue to step through using the Play button. Additionally, while it is running, you can press the Stop button or Skip button to pause or skip the animation. The slider controls the animation speed, and the bottom set of buttons are data presets, to see how the algorithm works on different data. While the animation is playing, colored circles will represent what values the algorithm is currently comparing. The blue circle represents the current smallest value found that passthrough. The other circle will be red if a the compared value is larger than the current smallest and it will be green if it is smaller and therefore will become the new smallest value.

Selection Sort Time and Space Complexity

Selection Sort is a relatively simple algorithm, but is rarely used due to sorts of similar difficulty running faster, such as Insertion Sort. Along with Insertion Sort, Selection Sort is very inefficient on large sets of data.

The time complexity of Selection Sort is always $O(n^2)$, as regardless of the order of the data it has the same number of comparisons (try the In Order preset compared to the Reverse Order preset). The space complexity is always $O(1)$, similar to Insertion and Bubble Sort.