Home

›

Articles

›

Selection Sort Algorithm Explained, With Examples # 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(n2), 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…

What is selection sort?

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

What are the advantages of selection sort?

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

What are the drawbacks of selection sort?

Because it’s not very efficient, selection sort is inadequate in dealing with large data sets. Its efficiency doesn’t depend on input distribution, but this also means it’s inefficient in all cases, no matter how sorted the initial array is already. It’s also not a stable algorithm, meaning that the relative order of equal elements may not be preserved. All in all, there are superior sorting algorithms out there for most cases, which can adapt better to the input in question.

What situations are best for using 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 performs the same number of iterations, it may perform better than some other algorithms when sorting an array that’s already partially sorted, since taking the same amount of time is better than taking a longer time. If you don’t require a stable sorting algorithm, selection sort is a viable choice.

What is the time complexity of selection sort?

The time complexity of selection sort is quadratic, represented as O(n2).

What is the space complexity of 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. While the algorithm can be inefficient, the space complexity means that it has advantages in situations where memory usage is constrained.

What are some alternatives to selection sort?

Many other sorting algorithms will be more efficient in most use cases. These include merge sort, quick sort and heap sort. These algorithms tend to be more adaptive, and have much better time complexity. Of these alternatives, merge sort is the only stable algorithm, so is viable where you need to preserve the relative order of equal elements.

Is selection sort a stable algorithm?

No, it’s not a stable algorithm. This means that, when sorting an array, elements of equal value may not be preserved in their original order after swapping occurs. #### Duncan Dodsworth, Author for History-Computer

Duncan Dodsworth is a writer at History Computer, primarly producing content about personal tech, computers or gaming. Duncan has been writing about tech for over 5 years since he majored in Chemistry in 2016. A resident of London, England, Duncan likes listening to music, playing around with gadgets and reading books half as often as he says he does.