Sorting Algorithms 101: Selection Sort

Photo by Sophie Elvis on Unsplash

Hello, again! In today’s post I will be reviewing the sorting algorithm, Selection Sort. This is part 2 of my five-part sorting algorithm series. If you missed the first part on Bubble Sort, you can find a link to that article here. You don’t need to have background knowledge on Bubble Sort to understand today’s topic though, so don’t feel obligated to backtrack.

I’ve added a quick performance comparison of Bubble Sort and Selection Sort at the end of the article. Feel free to skip it if you aren’t familiar with Bubble Sort yet.

As for those who want a small recap on Bubble Sort — the algorithm finds the biggest unsorted number in its iteration and moves it to the end of the array. On the contrary to Bubble Sort, Selection Sort works almost completely opposite. How? Let’s find out below!

Selection Sort: How It Works

Selection Sort finds the smallest unsorted element in the iteration and moves it to the beginning of the array. Let’s take this list, for example:

list = [ 4, 7, 1, 6, 10, 8, 3, 9, 7, 5, 2 ]

In the first iteration, the algorithm will move the number 1 to the first position of the array. Then, the number 2 will be moved into the second position of the array during the second iteration. And so on, and so on.

To do this, the algorithm maintains two subarrays in the given array. One subarray will consist of sorted elements at the front, while the second subarray will be made up of unsorted elements. In each iteration, the smallest element from the unsorted subarray will be chosen and moved to the back of the sorted subarray.

To keep track of where we are and to determine which part of the list has already been sorted, a marker will be used.

Let’s look at the list again:

list = [ 4, 7, 1, 6, 10, 8, 3, 9, 7, 5, 2 ]
         ^
       marker

The marker should start at the beginning of the array, at index 0. In this example, at number 4.

During the first iteration, the first number of the list (4) will be compared to the number at the marker, which is also 4. Since it’s the same number, nothing happens and we move on to the next number, which is 7. Another comparison determines whether the number 7 is smaller than the number at the marker (4). 7 is not smaller than 4, so we move onto the next number, 1.

Since, 1 is smaller than the marker (4), we swap the two numbers. 1 moves to list[0], and becomes the new marker. Keep in mind that the marker is still at index 0 during this iteration. The list should now look like this:

# First Iteration
list = [ 1, 7, 4, 6, 10, 8, 3, 9, 7, 5, 2 ]
         ^
       marker

After the swap, we continue down the list where we left off and move to the next number, 6. Since 6 is not smaller than the marker (1), the algorithm moves on to the next number, 10, and so forth. Skipping ahead as 1 is the smallest number in the array, this iteration will end and we will have a sorted subarray containing, 1.

Right before the second iteration, we increment the spot of the marker by one, moving it to index list[1], which is 7 in list. We now know that everything to the left of the marker is part of the sorted subarray, and everything to the right is unsorted. So, we start the comparison at the marker again and move down the unsorted subarray.

# Second Iteration
list = [ 1, 7, 4, 6, 10, 8, 3, 9, 7, 5, 2 ]
            ^
          marker

Since, the first number of the unsorted list is 7, the same element as our marker, we move onto the next number (4). 4 is smaller than 7, so, the two swap places, and 4 moves into the place of the marker.

# Second Iteration
list = [ 1, 4, 7, 6, 10, 8, 3, 9, 7, 5, 2 ]
            ^
          marker

Nothing happens as we move down the next few elements until we encounter 3. Since 3 is smaller than 4, another swap happens and 3 is now the marker.

# Second Iteration
list = [ 1, 3, 7, 6, 10, 8, 4, 9, 7, 5, 2 ]
            ^
          marker

Again, nothing happens until we encounter 2 at the very end of the list. A final swap happens in this second iteration, leaving us with this list:

# Second Iteration
list = [ 1, 2, 7, 6, 10, 8, 4, 9, 7, 5, 3 ]
            ^
          marker

The comparing and swapping will repeat through each iteration until the marker increments beyond the length of the array, thereby stopping the sorting algorithm and returning a fully sorted list!

# Sorted List
list = [ 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10]

Time Complexity

Selection Sort has a time complexity or big O notation of O(n2).

Why O(n2)?

The list or array comprises of n elements. In each iteration, the algorithm runs through each element. As we need to loop and iterate the same number of times as the length of the array (n), time complexity is (n x n) or (n2).

Time complexity may be a little strange now, but hopefully by the time we build out our own Selection Sort algorithm, it’ll make more sense. The general rule of thumb is to assign n to each loop that runs and multiply them together. What loops? Let’s move forward to find out.

Algorithm

I’ll be using Python for the code below, but feel free to use your language of choice. The general logic should be the same.

We’ll start by creating the marker first and assigning it a value of 0. This is to point the marker to the beginning of the array, at index 0.

def selection_sort(arr):
    marker = 0

We can then add in an if-statement to compare the first element (arr[0]) to the element at the marker (arr[marker]).

def selection_sort(arr):
    marker = 0
    if arr[0] < arr[marker]:

If the number is smaller than the element at the marker, then swap! I reassigned both values dynamically to achieve the swap.

def selection_sort(arr):
    marker = 0
    if arr[0] < arr[marker]:
        arr[marker], arr[0] = arr[0], arr[marker]

This is looking pretty good, but currently we are only comparing the first number in the array to our marker, which is also pointing to index 0. Let’s add in a for-loop so that we can iterate through all the elements in the array and be able to compare it to the marker.

def selection_sort(arr):
    marker = 0
    for num in range (marker, len(arr)):
        if arr[num] < arr[marker]:
            arr[marker], arr[num] = arr[num], arr[marker]

Now, this for-loop will only iterate through the array once. One iteration won’t sort our list, however (at least not in most cases), and we will need to iterate through the array n times to theoretically fully sort the list. To have the algorithm iterate through the array n times, we’ll add a while-loop.

def selection_sort(arr):
    marker = 0
    while marker < len(arr):
        for num in range (marker, len(arr)):
            if arr[num] < arr[marker]:
                arr[marker], arr[num] = arr[num], arr[marker]

Remember, the marker points to an index of the array. So, while the marker is less than the length of the array, we’ll enter the for-loop which will start each iteration into the array.

Quickly going back to time complexity, the while-loop represents having to go through (n) elements, and the for-loop represents having to go through another (n) elements. This makes (n x n). This is making a little more sense now, right?

Finally, our last step is to increment the marker. Without incrementing the marker, each element will remain being compared to index 0!

def selection_sort(arr):
    marker = 0
    while marker < len(arr):
        for num in range (marker, len(arr)):
            if arr[num] < arr[marker]:
                arr[marker], arr[num] = arr[num], arr[marker]
        marker += 1
        print(arr)

There, all done.

I ended the function by printing the array, but it’s certainly not necessary, depending on what you choose to do with the sorting algorithm.

Performance Comparison : Selection vs. Bubble Sort

With a marker in play, this algorithm is slightly more complicated than Bubble Sort. Because of this, while both Selection Sort and Bubble Sort perform similarly (O(n2)), Bubble Sort’s performance complexity can also be achieved at O(n) in its best case scenario. The best case scenario being that the list is already sorted, so the algorithm only needs to iterate through the array once.

This will never be the case for Selection Sort since the algorithm will continue to iterate through each number of the array n times, despite it already being fully sorted.

So why would you ever choose to use Selection Sort over Bubble Sort?

In the simplest terms, Bubble Sort consumes additional space for storing temporary variables and needs more swaps. Due to this, Bubble Sort is still considered to be the most simple and inefficient algorithm. Bubble Sort may be more efficient in its best case scenario, but best case scenarios rarely happen.

If you haven’t gotten the chance to familiarize yourself with Bubble Sort yet, definitely check it out. Again, you can find a link to my review on Bubble Sort here.

Hopefully you are starting to get a little more comfortable with sorting algorithms because we have three more to go after this. Next up, Insertion Sort! Stay tuned and thanks for reading!