Selection Sort: Explanation and Implementation in Python

Selection Sort is another sorting algorithm, so it will have the same goal as Bubble Sort, which I wrote about last week in this article.

The Goal of Selection Sort

Given an array of unsorted values, sort them so that they end up in ascending order. For example, if we have an array with the values [5, 8, 6, 4], we want it to end up in the order [4, 5, 6, 8].

The Steps of Selection Sort

1. We start off by assuming that the lowest value we've encountered so far is found in the right-most cell in the array. Then we look at each cell in the array from left to right, and compare each value to the lowest value so far, to check to see if we encounter a lower value. If we do encounter a lower value, then we'll store the index of that value in a variable, to use it later.
   • For example, in the array [5, 8, 6, 4], we start off with 5 as the lowest value so far. We compare 5 to 8, 5 is still less than 8, so we continue to 6, 5 is still less than 6 so we continue to 4. When we compare 5 to 4 we see that 4 is the lesser value, so we save the index of 4 as our lowest value.
2. Now that we've determined the index of the lowest value, we swap the position of the lowest value with the value we began the pass-through with.
   • For example, we started our pass-through with 5, and we now know our lowest value is 4, so we swap out 5 for 4, and now our array looks like this: [4, 5, 8, 6]
3. Each pass-through contains steps 1 and 2. We repeat the pass-throughs until we get a pass-through that would start at the end of the array, at which point we know the entire array has been sorted.

Implementation of Selection Sort

def selection_sort(array):
    n = len(array)
    for i in range(n): 
        # start off at first index of array and assume it's lowest value 
        lowest_so_far = i

        #compare each value in rest of array to lowest_value_so_far
        for j in range(i+1, n): 
            if array[j] < array[lowest_so_far]: 
                # if a new lowest value is found, record that value's index
                lowest_so_far = j
        # swap
        array[i], array[lowest_so_far] = array[lowest_so_far], array[i]


    return array

Code Explanation

1. We define our function which takes as its parameter an array
2. We save the length of the array in a variable called n
3. We begin an outer loop, which goes from the beginning of the array until one before the last item in the array (because the range function in Python is not inclusive of the number passed into it)
4. We save the index i to the variable lowest_so_far to keep track of the lowest value we've encountered in the array
5. We begin another loop which starts at the second value in the array and goes to the end of the array.
6. Starting with the second value in the array (at index j), we compare each item in the array to lowest_so_far
7. If we encounter a new lowest value, we save it's index in the variable lowest_so_far
8. Once we have the new lowest_so_far value, we can perform the swap
9. When we've gone through the entire array, up until the last value, we know it is sorted, so we can finally return the array

A quick word about efficiency of Selection Sort

I'm not going to dive into an explanation of Big O in this article, but I'll mention that the efficiency of Selection Sort is O(N² ). Bubble Sort and Selection sort are considered the same category of algorithm in terms of Big O, as they both represent quadratic time. However, Selection Sort does perform a little faster than Bubble Sort, in terms of how many actual steps it takes in an average scenario.

Resources

• The above article was developed from my notes on the chapter about Selection Sort in A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow - see Chapter 5 for a much more detailed explanation of the efficiency of Selection Sort, which I just touched on very briefly
• An article on Selection Sort from Educative.io