Sorting Algorithms: Selection Sort

Let’s Sort! In this series, I’ll be covering sorting algorithms. Most programming languages will come with a built-in sort function but in order to write better code, you need to know what’s going on in the background. If you are preparing for software engineering interviews, it’s very likely that one or more sorting algorithms may come up during your interviews. The sorting algorithms I’ll be covering in this series are:

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Merge Sort
5. Quick Sort
6. Radix/Bucket Sort
7. Heap Sort

What is Selection Sort?

Selection Sort is the third in our list of easy-to-understand algorithms (Bubble Sort and Insertion Sort being the first two). Similar to Bubble and Insertion sorting algorithms, Selection Sort is not a fast algorithm but nonetheless, important to know.

How Does it Work?

Let’s go back to the array example that we’ve used in our previous sections:

The way we are going to sort this list is by dividing it into two separate lists within that list. One sublist will represent our sorted numbers and the other will represent our unsorted numbers. Initially, our entire array represents the unsorted list.

We are going to search through our array for the smallest number. Once we have found the smallest number, we append it to our sorted list (i.e. make room for it in the beginning of the array). This happens in-place in the input array.

If we traverse through our array, we start at index 0 and consider whatever is there as our smallest value.

Continue to traverse the array and if you find any value that is smaller than what is saved before, change the smallest value to the new one. So if smallest=6 and we go to the next index, we see that 3 is smaller than 6 so smallest now equals 3. Continue through the entire array until you have found the smallest value. In our case, we find that 2 is the smallest value.

Now what? Take the leftmost value and swap it with your smallest value. Your array is now split in two: the blue portion is the sorted array and the rest is the unsorted array. Let’s see another iteration:

This time our unsorted array starts from index 1 because our sorted array has reserved index 0. We set smallest to what is in index 1 (smallest=3). We will compare smallest with every other value in the array, if there is any value that is smaller, we set smallest to that value. In this case, we see that 3 is the smallest value. We don’t need to swap 3 with itself so 3 now becomes part of the sorted array.

Next iteration:

We start at index 2 with smallest= 9. After going through the whole array, we find that 4 is the smallest value. 9 and 4 swap.

We continue to increase the size of our sorted array in this manner until we get the fully sorted array:

Time and Space Complexity

To sort an array with Selection Sort, you must iterate through the array once for every value you have in the array.

If we have n values in our array, Selection Sort has a time complexity of O(n²) in the worst case. In the best case, we already have a sorted array but we need to go through the array O(n²) times to be sure! Therefore Selection Sort’s best and worst case time complexity are the same.

What about space complexity? Selection Sort sorts in-place, meaning we do not need to allocate any memory for the sort to occur. Space complexity is O(1).

Code Implementation

Let’s look at Selection Sort in Python:

We define our selectionSort function and it takes in an array of integers. Now we need to start iterating through our array. Set whatever is at index 0 as smallest.

def selectionSort(array):
    for i in range(len(array)):
        smallest = array[i]
        smallestIdx = i

Then check the rest of the array for any smaller value. After we finish iterating through the whole array, swap the smallest value with the current value at i:

def selectionSort(array):
    for i in range(len(array)):
        smallest = array[i]
        smallestIdx = i        
        for j in range(i + 1, len(array)):
            if array[j] < smallest:
                smallest = array[j]
                smallestIdx = j
        array[i], array[smallestIdx] = array[smallestIdx], array[i]
    return array

And that is Selection Sort. It’s very simple but it’s also slow. It’s important to learn and hopefully, it will help you understand why some sorting algorithms are more optimal than others.

Thanks for reading!

References

Selection Sort - GeeksforGeeks