Selection Sort: Implementation and Analysis

Photo by Héctor J. Rivas on Unsplash

Sorting plays an important role in any computer application. When processing large amounts of data, by using efficient sorting algorithms we can bring order to our data, which streamlines our data analysis process. Today, we will dive deep into one such sorting algorithm — selection sort (for more algorithms, head over to https://getsetcode.blog/algorithms/)

Selection sort: Definition

Selection sort is one of the easier algorithms to understand. Let’s first look into how this algorithm works, then analyze the time it takes to process data, and finally understand how this efficiency changes as we pump in more data. We will also implement the algorithm in C#.

Selection sort works on the Array data structure, and a simple definition would be as follows — “For N elements in an array, loop N-1 times, and in each iteration, select the smallest element and bring it to the first index of that iteration”

Let’s jump right into an example and work our way through to understand the algorithm.

We wish to sort the following array:

As per the definition,

1. We are going to loop 4 times (N-1 times). Let’s call 1 loop as 1 iteration of the array
2. In every iteration, we are going to find the smallest element, and bring it to the starting position of the iteration.

In order to accomplish the above, let’s define the variable start to track the start position of every iteration, and also let’s define the variable min to track the minimum element in one iteration.

To begin, Let’s initialize start at index 0, and also min equal to the element at index 0:

Iteration 1

We now start iterating the array. Whenever we move to the next element, we check if that element is less than our min element. If yes, we assign that element to min. If not, min remains unchanged and we keep moving forward to the next element. We will do this till we reach the last element of the array:

note that start will always point to the first position of the array

We have now reached the last element of the array, and have identified the smallest element “0” at index 3.

As a last step in this iteration, we will swap the minimum element, with the element at the start position:

This will give us the following array, with the minimum element at the first position. Note that at this point we have sorted the first element. Let’s gray out the first element to highlight that it has been sorted and from the next iteration we do not need to look at this element.

Iteration 2

We were able to sort one element in the last iteration, but we have four more elements to go! Since, the element at index 0 is already sorted, we will begin this iteration from index 1. Let’s initialize our start and min variables again:

Like we did last time, we will iterate through the array, checking for the minimum element at each index, until we reach the end of the array:

We have now reached the last element of the array, and have identified the smallest element at index 4. As we did in the last iteration, we will swap this smallest element with the element at the start position of this iteration:

After this step, we now have the first two elements in our array at correct or sorted positions:

Now that we have got a hang of the algorithm, let’s quickly do all the remaining iterations.

Iteration 3

Iteration 4

Note that in this iteration, the minimum element identified is “5”, which is at index 3, which is also the start index of this iteration. Thus, the minimum element is already at its correct position, and we do not need to swap it with any other element:

The 4th iteration was our last iteration. We sorted 4 elements in these iterations. We are just left with the last element, and since all the other elements are sorted, we can safely say that the last element is also in the correct position. This is why the selection sort runs N-1 iterations for N elements.

Quick Recap

1. For N elements, the algorithm runs N-1 iterations
2. For each iteration, we identify the start position and assign the min element to be equal to the element at that start position
3. We iterate through the array till the last element. For every element we check if it is less than the min element. If yes, we replace the min element
4. At the end of the iteration, we have identified the min element and we swap it with the element at the start position

Implementation in C#

Here’s an implementation of the algorithm in C#.

• arr represents the array to be sorted
• start represents the start position of the array. With every iteration, we will increment start by 1. The algorithm will run until start reaches the end of the array
• min represents the index of the minimum element. We initialize this equal to the start position.

Let’s break the code into pieces to understand it better:

1. We will run the algorithm until start reaches the end of the array:

2. The for loop below represents one iteration. We initialize min to be equal to the start index. We then go through each and every element starting from “start + 1” index and until the end of the array. We compare each element with the element at the “min” index. If we find a smaller element, we re-assign the min index

3. Finally, if the min index is different from the start index, we swap the elements at both these indexes to bring the smallest element to the first position:

on running the above algorithm, we get the sorted array:

Complexity Analysis

We have three primary operations in selection sort:

1. Iterations — In our example of 5 elements, we did 4 iterations. Thus we can say that for N elements, selection sort will run N-1 iterations
2. Swaps — At the end of every iteration, we performed one swap — the minimum element was swapped with the element at the first position
3. Comparisons — comparison is the operation when we check if each element is smaller than the minimum element. For our first iteration, we did 4 comparisons, for the second iteration we did 3, for third iteration we did 2 comparisons and for the 4th iteration we did 1 comparison. In other words we did: (N-1) + (N-2) + (N-3) … + 1 comparisons.

For 1 iteration, we did: 1 swap + N-1 comparisons

For (N-1) iterations, we will do approximately: (N-1) * (1 swap + N-1 comparisons )

If we ignore all the constants in the above equation, we will get N * N, or N squared (N²).

Thus, the complexity of selection sort is O(N²).

Efficiency of Algorithm with increasing data

We derived the complexity of the algorithm as N squared. If we plug in numbers, we can see how the number of operations that the algorithm takes increases:

N = 5, N² = 25

N = 10, N² = 100

N = 15, N² = 225

This shows that by increasing the number of elements by 5, we are increasing the number of operations at a really fast pace. Just by going from 5 to 10 elements, we increased the number of operations by 75! When we went from 10 to 15 elements, we increased the number of operations by 125!

Thus, as the data increases, the algorithm efficiency decreases and so selection sort is not a good choice when it comes to sorting huge amounts of data.

Summary

• Selection sort works on array data structures. It loops through the array N-1 times, and in each loop finds the smallest element. This element is swapped by the element at the first position.
• The primary operations in this algorithm are iterations, swaps and comparisons. By calculating the number of operations, we can derive the complexity of selection sort as O(N²)
• As we increase input data, the number of operations done by the algorithm increases at a much faster rate, making selection sort a bad choice for large amounts of data.