The selection sort algorithm is explained with examples

There are many sorting algorithms that can be used to sort datasets. Usually this data is presented in a list or table. Among these algorithms, the selection sort algorithm is one of the easiest to understand and implement. In this article, we’ll explain the theory of selection sort, its implementation, and best practices for using the algorithm.

What is Selection Sort?

Selection sort is a comparison-based sorting algorithm. It works by splitting 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 item can also be selected first, depending on whether you want your list to be in ascending or descending order. This is an iterative process, which means that the method is repeated until all elements are placed in the sorted array in their correct positions. As you might expect, with each iteration the size of the sorted subarray increases by one element, while the size of the unsorted array decreases by one element.

The algorithm behind the Sort selection

The algorithm behind selection sorting is quite simple and follows these steps:

1. The minimum element in the unsorted array is found and swapped with the first element at index 0.
2. The unsorted array is then traversed to find the new minimum element.
3. If an element smaller than the element at index 0 is found, the elements are swapped.
4. The next smallest 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.

How selection sorting works

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

If we look at the table [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 that the first index is set to 0, not 1).

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

[21, 61, 59, 47, 72]

where green = sorted item

For the second pass, we find that 47 is the second smallest value. This is then exchanged with 61.

[21, 47, 59, 61, 72]

The third pass finds that 59 is the third element already in position. Therefore no exchange takes place.

[21, 47, 59, 61, 72]

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

[21, 47, 59, 61, 72]

The fifth and final pass does much the same. 72 is the fifth smallest or largest element and is in the correct position. The array is now fully sorted in ascending order.

[21, 47, 59, 61, 72]

Selection sort implementation

We can implement sort by selection with various programming languages, including the most common ones – C, C++, C#, PHP, Java, JavaScript, and Python. For illustration we will 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)

Code Explanation

An explanation of the code used would be helpful at this point. First we define the “Ssort” function as an array function of a certain size.

The “for” loop dictates that it will start a loop that will iterate over a range of “size”, ie. the length of the array. The “step” variable indicates that each iteration will take the 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 following “for” loop specifies a loop that will traverse the unsorted array starting at “step + 1”. This is because the “step” element is already placed in the sorted array. The variable “i” in each iteration will be equivalent to step + 1, step + 2, and so on up to size – 1.

The ‘if’ operator which checks if the current element in ‘i’ is less than the current minimum element. If this is found to be the case, the minimum element is updated to reflect this.

Finally, this rather complex line has a simple meaning. After the previous loop completes, the minimum unsorted element is swapped with the first unsorted element of the array. This effectively adds the element to the end of the sorted array.

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

Whenever you use Python, it’s important to use the correct indentation to indicate different operations. Otherwise, you will receive an error message and the calculation will not be performed.

What the code looks like

See the screenshot below to see what this code looks like when implemented in Python.

Selection sorting algorithm explained, with examples FAQ (Frequently Asked Questions)

What is selection sort?

Selection sort is a simple sorting algorithm that sorts an array of elements in ascending or descending order. It does this by traversing the array to find the minimum element and swapping it with the element at index 0 in the sorted subarray. The unsorted subarray is then traversed again and the minimal element is found and swapped into its correct position. The algorithm repeats this process until the entire array is sorted. Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning of the sorted part of the array. The algorithm supports two subarrays in a given array.

What are the advantages of selective sorting?

Selection sort is a very simple algorithm to understand and implement and is sufficient for very small data sets.

What are the disadvantages of selection sorting?

Because it is not very efficient, selection sort is inadequate for working with large data sets. Its efficiency does not depend on the allocation of records, but it also means that it is inefficient in all cases, regardless of the sorting of the initial array. It is also not a robust algorithm, meaning that the relative order of equal elements may not be preserved. In general, in most cases there are superior sorting algorithms that can better adapt to the input in question.

What are the best situations to use selection sort?

Selection sort is best used when the input size is small and you want a simple and relatively efficient solution. Since the space complexity is O(1), selection sort has advantages if memory usage is something you need to watch. Because it always runs the same number of iterations, it can perform better than some other algorithms when sorting an already partially sorted array, because taking the same time is better than taking more time. If you don’t need a robust sorting algorithm, selection sort is a viable choice.

What is the time complexity of sorting the selection?

The time complexity of selection sorting is quadratic, represented by O(n²).

What is the spatial complexity of the selection sort?

The space complexity is O(1). This means that a constant amount of memory is used for each iteration, since only one temporary variable needs to be stored. Although the algorithm may be inefficient, the spatial complexity means that it has advantages in situations where memory usage is limited.

What are the alternatives to selection sort?

Many other sorting algorithms will be more efficient for most use cases. These include merge sort, quick sort, and bulk sort. These algorithms are usually more adaptive and have much better time complexity. Of these alternatives, merge sort is the only robust algorithm, so it is viable when you need to preserve the relative order of equal elements.

Is selection sort a robust algorithm?

No, it is not a stable algorithm. This means that when sorting an array, elements with the same value may not keep their original order after swapping.