Selection Sort

Concept

Selection Sort is the logical opposite of Bubble Sort.
Instead of heavily swapping adjacent elements to push the largest number to the back, Selection Sort scans the entire array, finds the absolute minimum element, and explicitly swaps it with the very first index. It then locks that first index, and scans the rest of the array for the second smallest element.

The Mechanism

Array: [5, 3, 8, 4, 2]

Pass 1:

• Pointer is at Index 0 (Value 5).
• Scan the rest of the array: [3, 8, 4, 2].
• The absolute minimum value in that slice is 2 (Index 4).
• Swap Index 0 with Index 4.
• Array becomes [2, 3, 8, 4, 5]. Index 0 is permanently locked!

Pass 2:

• Pointer moves to Index 1 (Value 3).
• Scan the rest of the array: [8, 4, 5].
• The absolute minimum is 4 (Index 3). Wait! The current value 3 is actually smaller than 4.
• The minimum is already in the correct place. Do not swap. Index 1 is locked!

Implementation

// Time Complexity: O(N^2) (Always, Best/Worst/Average are identical)
// Space Complexity: O(1) In-Place

function selectionSort(nums: number[]): number[] {
    const n = nums.length;

    // We don't need to check the very last element, 
    // because it will mathematically be the largest one left!
    for (let i = 0; i < n - 1; i++) {
        let minIndex = i; // Assume the current index is the smallest

        // Scan the rest of the unsorted array to find a smaller one
        for (let j = i + 1; j < n; j++) {
            if (nums[j] < nums[minIndex]) {
                minIndex = j; // We found a new minimum candidate!
            }
        }

        // If we found a smaller number, swap them!
        if (minIndex !== i) {
            [nums[i], nums[minIndex]] = [nums[minIndex], nums[i]];
        }
    }

    return nums;
}

Why it’s Terrible

Like Bubble Sort, Selection Sort is $O(N^2)$.
However, unlike Bubble Sort, Selection Sort cannot be optimized. Even if you hand it a perfectly sorted array [1, 2, 3, 4], it blindly scans the entire remainder of the array every single time to ensure there isn’t a smaller number hiding at the end. It takes $O(N^2)$ time in its absolute Best-Case scenario.

The only theoretical advantage of Selection Sort over Bubble Sort is the number of Swaps.
Bubble Sort executes massive amounts of rapid-fire swaps (writing to memory over and over).
Selection Sort only executes exactly One Swap per pass. If writing to memory is extremely expensive in a specific hardware architecture (like old EEPROM/Flash memory), Selection Sort causes significantly less hardware wear-and-tear than Bubble Sort.

Interview Questions

Q: Is Selection Sort Stable?
A: No, it is Unstable.
Consider the array: [5A, 5B, 2].
Pass 1: It scans the array, finds the minimum 2, and swaps it with the first element 5A.
The array becomes [2, 5B, 5A].
The relative order of 5A and 5B has been destroyed! 5B now comes first.

Q: What is the primary difference in behavior between Bubble Sort and Selection Sort?
A: Bubble Sort sorts the array backwards. The absolute largest elements bubble to the end, locking the end of the array first. Selection Sort sorts the array forwards. It finds the absolute smallest elements and locks the front of the array first.