Selection Sort Algorithm Explained, With Examples

There are many sorting algorithms that can be used to sort data sets. Typically, this data is presented in a list or array. Of these algorithms, the selection sort algorithm is one of the simplest to understand and implement. In this article, we’re going to explain the theory behind selection sort, how it’s implemented, and best practices for using the algorithm.

What is Selection Sort?

Selection sort is a comparison-based sorting algorithm. It works by dividing the array into two parts – sorted and unsorted. The element with the smallest value is selected, and placed at index 0 of the sorted subarray. The largest element can also be selected first, depending on whether you desire your list to be in ascending or descending order. This is an iterative process, meaning the method is repeated until all elements are placed into the sorted array in their correct positions. As you can expect, with each iteration the sorted subarray size increases by one element, while the unsorted array size decreases by one element.

The Algorithm Behind Selection Sort

The algorithm behind selection sort is fairly simple, and follows these steps:

1. The minimum element in the unsorted array is found and swapped with the first element, in index 0.
2. The unsort array is then traversed to find the new minimum element.
3. If any element is found to be smaller than the element in index 0, the elements are swapped.
4. The next minimum element in the unsorted array is found, and added to the sorted subarray, following the previous constraint.
5. This process is repeated until the entire array is sorted.

Working of Selection Sort

Now we’ve covered how selection sort works, it’s time to illustrate this with an example.

If we consider the array [72, 61, 59, 47, 21]:

The first pass, or iteration, of the process involves traversing the entire array from index 0 to index 4 (remember the first index is set to 0, not 1).

The minimum element found is 21, so this is swapped with the first element, 72. This is illustrated below.

[21, 61, 59, 47, 72]

where green = sorted element

For the second pass, we find 47 to be the second smallest value. This is then swapped with 61.

[21, 47, 59, 61, 72]

The third pass detects 59 to be the third element, which is already in position. Therefore, no swap occurs.

[21, 47, 59, 61, 72]

The fourth pass finds 61 to be the fourth element which, again, is already in place.

[21, 47, 59, 61, 72]

The fifth and final pass results in much the same. 72 is the fifth smallest, or the largest element, and is in the correct position. Now, the array is completely sorted in ascending order.

[21, 47, 59, 61, 72]

Implementation of Selection Sort

We can implement selection sort with a variety of programming languages, including the most common – C, C++, C#, PHP, Java, Javascript, and Python. For illustration, we’re going to use Python. The code used with Python is as follows:

def SSort(arr, size):
   
    for step in range(size):
        min_idx = step

        for i in range(step + 1, size):
           if arr[i] < arr[min_idx]:
                min_idx = i
         
        (arr[step], arr[min_idx]) = (arr[min_idx], arr[step])


data = [-7, 39, 0, 14, 7]
size = len(data)
SSort(data, size)
print('Ascending Sorted Array:')
print(data)

Explanation of the Code

At this stage, an explanation of the code used will be helpful. Firstly, we define the function “SSort” as a function of an array with a specified size.

The “for” loop dictates that a loop will begin that will iterate over a range of “size”, meaning the length of the array. The “step” variable indicates that each iteration will take on values 0, 1, 2… up to size-1.

The next line shows that the initial value of “step” is equal to the variable “min_idx”. This is a way to keep track of the position of the minimum element in the unsorted array.

The next “for” loop specifies a loop that will iterate over the unsorted array, beginning at “step + 1”. This is because the “step” element is already placed in the sorted array. The “i” variable in each iteration will be equivalent to step + 1, step + 2 and so on up to size – 1.

The “if” statement that checks if the current element at “i” is less than the current minimum element. If this is found to be the case, the minimum element is updated to reflect this.

Lastly, this rather complicated line has a simple meaning. Once the previous loop has finished, the minimum unsorted element is swapped with the first element in the unsorted array. This effectively adds the element to the end of the sorted array.

The code at the bottom simply dictates the array that we’re working with, of length “size”, and calls selection sort to work on this array. The output is then printed with the title “Ascending Sorted Array”.

Whenever using Python, it’s critical that you use the correct indentation to designate the separate operations. Otherwise, you’ll receive an error message and the computation won’t run.

What the Code Looks Like

Check out the screenshot below to see how this code looks when implemented in Python.

Best and Worst Use Cases of Insertion Sort

While insertion sort is useful for many purposes, like with any algorithm, it has its best and worst cases. This is mostly down to time and space complexity.

Time Complexity with Insertion Sort

Time complexity in each case can be described in the following table:

Like with any algorithm, selection sort has its own time and space complexity. This basically refers to how the complexity, or speed of execution, changes in a variety of cases. The time complexity can be summarized as in the following table:

The best case refers to when the array is sorted, the average case refers to when the array is jumbled, and the worst case refers to when the array is in either ascending or descending order and you desire the opposite order. In other words, they refer to how many iterations will be needed to complete the process, with the worst case requiring the maximum number of iterations.

For this case, the time complexity is identical for selection sort in every case. This is because the algorithm always performs the same number of comparisons and swaps, no matter how sorted the array is. Therefore, the complexity is O(n²), also known as quadratic time. This is a major reason why the algorithm isn’t very efficient as far as sorting algorithms go, but it also means that the efficiency isn’t dependent on the distribution of the input.

Space Complexity with Selection Sort

Space complexity refers to how much memory is required for the computations. In the case of selection sort, this is equal to O(1). This means that a constant amount of memory is required, independent of input size. The only temporary variable being stored is “min_idx”, which doesn’t change with increasing input size.

Wrapping Up

Selection sort is a relatively simple but fairly inefficient algorithm for sorting elements in a given input. It’s mostly appropriate for very small data sets, and can be implemented with a variety of programming languages. Selection sort works by splitting the array into two subarrays, sorted and unsorted. The process then traverses through an array to find the minimum element, and moves this element to index 0. The process is repeated, finding the second and third smallest elements and so on and swapping them into their correct index positions. This continues until the entire array is sorted.

Up Next…

• Python Tuples vs Lists: 5 Key Differences and When to Use Each
• What Is Insertion Sort, and How Does It Work?
• What’s the Difference between a Frontend and Backend Developer?

The image featured at the top of this post is ©iStock.com/Buffik.