Sorting Problem: Selection Sort

Selection sort

Let’s discuss the idea of the selection sort algorithm:

1. Find the minimum value index and place it at the first index (by swapping the first location’s value with the minimum).

2. Now find the 2nd minimum (by ignoring the first index because the minimum is already placed on the first index, that is, find the minimum value index between the range of the second index till the last) and place it on the 2nd index (by swapping the 2nd minimum value with the second index value).

3. Similarly, place the 3rd minimum at the third location, and so on.

Before we move to its implementation, notice that the central theme of this sorting algorithm lies in selecting the minimum index within a range.

Selecting minimum in a range

To find the minimum index mi within a range of A[si ... ei] (where si is the start index and ei is the end index), we select the min as A[si] and mi=si. Then we keep updating min after comparing it with each element A[i] where $i>si$. If min<A[i], update min = A[i].