Sorting Problem: Selection Sort

We will learn to write programs with basic selection sort strategies and see where we should apply them.

We'll cover the following

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>sii>si. If min<A[i], update min = A[i].

Press + to interact
// Finding minimum in the range of [si...ei]
int min = A[si];
int mi = si;   // let's call the first value as minimum
for(int i=si+1; i<=ei; i++)
{
    if(min>A[i])
        min = A[i], mi = i;
}
// mi will have the index of the min value within the range [si..ei]

When the loop ends, mi will hold the minimum value index within range A[si...ei].

Completing the selection sort

How to place the sith minimum index that is held by mi?

We can just do this: swap(A[si], A[mi]).

Here is the complete algorithm for the selection sort.

Press + to interact
for(int s = 0; s<size; s++)
{
    int si = s, ei = size-1;   // For each iteration the range will shrink
            
    int min = A[si], mi = si;
    
    for(int i=si+1; i<=ei; i++)
    {
        if(min>A[i])
            min = A[i], mi = i;
    }
    // Place the sth minimum element(i.e. the value at mi) at sth index
    swap(A[s], A[mi]);
}

Look at the animation of selection sort below:

Instruction: Here is the playground. Write the entire code and play with several inputs to see how the code is acting. 

7 3 5 2 3 5 7 9
Selection sort solution

Selection sort function

If you look closely, it is not hard to see that the nested 2nd function is doing the selection of the minimum in the range and the outer loop is just driving that range to find the next sith minimum value. We can make that selection a separate function and clean our implementation.

Let’s look at the cleaner functional implementation:

7 3 5 2 3 5 7 9
Selection sort (functional approach)

Quiz–Selection sort

Selection sort

1

How many swaps are enough to complete the sorting using the selection sort algorithm?

A)

size-1 times.

B)

size times.

Question 1 of 50 attempted

Hurray! you are done with discovering two of the very famous sorting algorithms.