Selection Sort

What is Selection Sort?

Selection sort is a comparison-based sorting algorithm that divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list, and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

info

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.

You many learn decision trees in future (entry level topic in AI/ML), and you could reach a conclusion with decision tree that the number of comparisons that a comparison sort algorithm requires increases in proportion to $n\log(n)$, where $n$ is the number of elements to sort.

How Does Selection Sort Work?

Here's a step-by-step breakdown of how the selection sort algorithm operates:

1. Start at the beginning of the array.
2. Find the smallest element in the array from the current position to the end.
3. Swap the smallest element found with the element at the current position.
4. Move the current position one forward, effectively growing the sorted portion of the array and shrinking the unsorted portion.
5. Repeat the process for each element until the array is fully sorted.

Implementation

selection sort in increasing array

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        int min_idx = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // Swap the found minimum element with the first element
        swap(arr[min_idx], arr[i]);
    }
}

Step by Step Example

Analysis of Selection Sort

Note that for item from index i to the end of the array, we need to perform a linear search to find the min within this range. Thus, the runtime complexity would always be in $O(n^2)$.

Here we discuss worst case time complexity and best case time complexity.