When playing a card game with cards in your hand, you might be the type of player who likes to sort the cards so that you know at a moments notice which card to use. You might go about sorting the cards by starting from the left, finding the smallest card and swapping it to that position. Then, doing the same with the next smallest, and so on until you have a hand of sorted cards. There is an algorithm for this methodology; Selection Sort!

Assumptions

  • Knowledge of Big-O notation
  • Familiarity with The Master Theorem is a plus!

What is Selection Sort?

Selection Sort is an in-place, unstable sorting algorithm that continuously searches for the next smallest item in an array to achieve sorted order.

> With modifications, selection sort can be made stable.

/* pseudo-code */
int[] array = { 7, 2, 4, 9, 3, 5, 8 }

function SelectionSort(int [] arr){
    // Iterate over the entire array, except the last element.
    for ( int i =0; i < arr.length - 1; i++ ){
        // Track the lowest element left in the array.
        int min = i;
        // Iterate the remaining array.
        for ( int j = i + 1; j < arr.length; j++ ){
            // If j is less than min, change the min index.
            if ( arr[j] < arr[min] ){
                min = j;
            }
        }
        // Do an in-place swap of i and the minimum.
        int tmp = arr[min];
        arr[min] = arr[i];
        arr[i] = tmp;
    }
}

Analyzing Selection Sort

An array of size n will require that every element is looked at to find the correct placement of element i. This means the array will be looped through n times, resulting in a runtime performance of O(n<sup>2</sup>).

Best/Worst/Average Memory
O(n<sup>2</sup>) O(1)

Sorting Cards

To visualize selection sort, let's go back to the hand of cards example. Say the dealer gives you a hand of seven cards and they're unsorted.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_SelectionSort_01.png" alt="unsorted cards" style="max-width:95%;">

</div>

To start sorting the cards using selection sort, scan from left to right and find the smallest card. Once you've done this, place it all the way to the left.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_SelectionSort_02.png" alt="first element sorted" style="max-width:95%;">

</div>

Repeat this process once more, placing the next smallest card after the first smallest. Now you know that at least the first two cards of the seven are in sorted order.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_SelectionSort_03.png" alt="first and second elements sorted" style="max-width:95%;">

</div>

Continuing this process for the remainder of the cards until you have seven cards in sorted order, and you're finished!

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_SelectionSort_04.png" alt="all elements sorted." style="max-width:95%;">

</div>

When to Use Selection Sort

Selection sort works well in scenarios where it takes more time for the computer to write to a spot of memory than it does to read that spot in memory, such as on flash memory. These factors do not make for a likely scenario in most cases though.

Further Resources