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:
- The minimum element in the unsorted array is found and swapped with the first element at index 0.
- The unsorted array is then traversed to find the new minimum element.
- If an element smaller than the element at index 0 is found, the elements are swapped.
- The next smallest element in the unsorted array is found and added to the sorted subarray, following the previous constraint.
- 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
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)
print('Ascending Sorted Array:')
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.
The best and worst use cases for insertion sort
Although insertion sort is useful for many purposes, as with any algorithm, it has its best and worst cases. This is mainly due to temporal and spatial complexity.
Time complexity with insertion sort
The time complexity in each case can be described in the following table:
Like any algorithm, choice sort has its own time and space complexity. It basically refers to how the complexity or speed of execution changes in different cases. The time complexity can be summarized in the following table:
|A case||Time complexity|
The best case applies when the array is sorted, the middle case applies when the array is shuffled, and the worst case applies when the array is in ascending or descending order and you want the reverse order. In other words, they refer to the number of iterations required to complete the process, with the worst case requiring the maximum number of iterations.
In this case, the time complexity is identical for sorting the selection in all cases. Indeed, the algorithm always performs the same number of comparisons and exchanges regardless of the sorting of the array. Hence the complexity is O(n2), also called quadratic time. This is a major reason why the algorithm is not very efficient when it comes to sorting algorithms, but it also means that the efficiency does not depend on the distribution of the input.
Spatial complexity with selection sort
Space complexity refers to the amount of memory required for computations. In case of selection sort, this is equal to O(1). This means that a constant amount of memory is required regardless of the size of the record. The only temporary variable stored is “min_idx”, which does not change as the record size increases.
Wrap it up
Selection sort is a relatively simple but rather inefficient algorithm for sorting the elements in a given input. It is mainly suitable for very small data sets and can be implemented with various programming languages. Selection sort works by dividing the array into two subarrays, sorted and unsorted. The process then loops through the array to find the smallest element and moves that element to index 0. The process repeats, finding the second and third smallest elements, and so on. and exchange into their correct index positions. This continues until the entire array is sorted.
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(n2).
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.