Selection sort is a simple sorting algorithm that performs an in-place sorting.
Suppose we sort an array in ascending order. The algorithm works as follows. First, it finds the smallest element in the whole array and exchange it with the element at the first position, then find the second smallest element and exchange it with the element at the second position, and continue in this way until the whole array is sorted.
If we want to sort the array in descending order we should find the largest element instead of smallest one.
If n is the length of an input array, the algorithm has asymptotic time complexity Ο(n2) in the worst and average cases in terms of the number of comparisons. It makes the algorithm inefficient for sorting large arrays. The algorithm finds the minimum/maximum element n - 1 times.
The basic implementation of the algorithm is unstable, but it can be modified to be stable.
How it works by example
Suppose we have an unsorted array of integers. We should sort it in the ascending order.
The array has six elements, the first element has the index 0, the last one has the index 5.
The following image illustrates how the sorting algorithm work. See some explanations below.
The sorting process using the selection sort algorithm (ascending)
There are some explanations for the image.
1) We find the min number in the whole array (11) and exchange the number with the first element (21). Now, the first element belongs to the sorted subarray.
2) We find the min number in the unsorted subarray (19) and exchange the number with the second element. Now, the first and second elements belong to the sorted subarray.
3) We find the min number in the unsorted subarray (21) and exchange the number with the third element (23). Now, the first three elements belong to the sorted subarray.
4-6) We repeat the same process until the whole array is sorted.
As you can see, the algorithm is quite simple. It never changes the already sorted subarray.
If you would like to see a visualization, click Selection Sort here.