Selection Sort

Selection Sort

Photo credit to Alex Block (alexblock on Unsplash)

Algorithm

  1. Initialize an index variable to zero, this represents the start of the array.

  2. Incrementally traverse the list to find the smallest value in the unsorted array.

  3. If the smallest value is not the last part of the sorted array, then swap the values.

  4. Increment the index variable to point to the next element in the unsorted array.

  5. Repeat steps 2-4 until the array is completely sorted.

Implementation

Follow the steps in the algorithm above, and use the comments for reference. Spend some time following each step carefully and you will understand it.

void selection_sort(std::vector<int> &v)
{
    for (int a = 0; a < v.size() - 1; a++)
    {
/* Index variable keeping track of sorted position */
        int min_index = a;
/* Traverse the array to find the smallest value */
        for (int b = a; b < v.size(); b++)
        {
            if (v[b] < v[min_index]) min_index = b;
        }
/* Swap the smallest value if there is one smaller */
        if (min_index != a) std::swap(v[a], v[min_index]);
    }
}

Time Complexity

The overall time complexity of the function is always squared as shown below, where n is the size of the input array.

$$\frac{n\times (n-1)}{2} \approx O(n^2)$$

The best-case scenario is a sorted array.

Best case:

Input => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Output => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

The worst-case scenario is a reverse sorted array.

Worst case:

Input => [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]

Output => [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

To increase the readability of the output I've added some print-to-terminal functionality. Both scenarios end up running through the inner loop n times at the last run.

user@machine:~$ g++ -o a sorting_algos.cpp 
user@machine:~$ ./a
|Test selection sort best case|
==============0==============
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,
2, 3, 4, 5, 6, 7, 8, 9,
3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9,
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============1==============
1, 2, 3, 4, 5, 6, 7, 8, 9,
2, 3, 4, 5, 6, 7, 8, 9,
3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9,
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============2==============
2, 3, 4, 5, 6, 7, 8, 9,
3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9,
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============3==============
3, 4, 5, 6, 7, 8, 9,
4, 5, 6, 7, 8, 9,
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============4==============
4, 5, 6, 7, 8, 9,
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============5==============
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============6==============
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============7==============
7, 8, 9,
8, 9,
9,
==============8==============
8, 9,
9,
|Test selection sort worst case|
==============0==============
9, 8, 7, 6, 5, 4, 3, 2, 1, 0,
8, 7, 6, 5, 4, 3, 2, 1, 0,
7, 6, 5, 4, 3, 2, 1, 0,
6, 5, 4, 3, 2, 1, 0,
5, 4, 3, 2, 1, 0,
4, 3, 2, 1, 0,
3, 2, 1, 0,
2, 1, 0,
1, 0,
0,
==============1==============
8, 7, 6, 5, 4, 3, 2, 1, 9,
7, 6, 5, 4, 3, 2, 1, 9,
6, 5, 4, 3, 2, 1, 9,
5, 4, 3, 2, 1, 9,
4, 3, 2, 1, 9,
3, 2, 1, 9,
2, 1, 9,
1, 9,
9,
==============2==============
7, 6, 5, 4, 3, 2, 8, 9,
6, 5, 4, 3, 2, 8, 9,
5, 4, 3, 2, 8, 9,
4, 3, 2, 8, 9,
3, 2, 8, 9,
2, 8, 9,
8, 9,
9,
==============3==============
6, 5, 4, 3, 7, 8, 9,
5, 4, 3, 7, 8, 9,
4, 3, 7, 8, 9,
3, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============4==============
5, 4, 6, 7, 8, 9,
4, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============5==============
5, 6, 7, 8, 9,
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============6==============
6, 7, 8, 9,
7, 8, 9,
8, 9,
9,
==============7==============
7, 8, 9,
8, 9,
9,
==============8==============
8, 9,
9,