Selection Sorting – How does it work internally?

If we HAVE to speak about Sorting Techniques, Selection Sorting is another important sorting–algorithm.

But first things first-

What is Sorting?

At its core, sorting is just the process of arranging a messy collection of items into a specific, meaningful order.

Here are two examples of sorting, we go through every day life:

• Numerical Order: Arranging numbers from smallest to largest (1, 2, 3…) or largest to smallest (99, 98, 97…).
• Alphabetical Order: Arranging words or strings from A to Z (like a phonebook contact list) or Z to A.

What is Selection Sorting?

Imagine you are holding a handful of unsorted playing cards, and you want to arrange them from smallest to largest. What’s your natural instinct? You scan through all the cards, find the absolute lowest one, and pull it to the very front. Then, you look at the remaining cards, find the next lowest one, and place it right behind the first.

That is exactly how Selection Sort works. In computer science, Selection Sort is a fundamental, comparison-based sorting algorithm that operates on a direct, scanning principle. Instead of continuously swapping adjacent elements, it repeatedly steps through the unorganized portion of a data structure, scans the remaining elements to identify the absolute minimum (or maximum) value, and performs a single swap to place it into its final, correct position.

By maintaining a growing, sorted subarray at the beginning of the structure and shrinking the unsorted boundary with each pass, it systematically organizes data with a highly predictable, deterministic execution pattern.

Why it’s better than Bubble Sort: While Bubble Sort frantically swaps elements constantly as it walks through the array, Selection Sort stays calm. It only makes one swap per pass, drastically reducing unnecessary memory writes!

Its characters include:

• In-Place Memory Execution

Selection Sort requires an auxiliary (extra) space complexity of O(1). It performs all its element swapping directly within the original array without needing to replicate or spawn temporary storage arrays.

• Predictable, Deterministic Performance

Unlike Bubble Sort or Insertion Sort, Selection Sort does not care if your data is already perfectly sorted, completely reversed, or totally random. Because it is forced to scan the entire remaining unsorted section every single time just to ensure it has found the true minimum, its time complexity is always fixed:

• Best Case: O($n^2$)
• Average Case: O($n^2$)
• Worst Case: O($n^2$)

• Highly Efficient for Memory Writes

While its comparison count is high O($n^2$), its swap count is exceptionally low. It performs a maximum of (n – 1) swaps in total. It only swaps data once per full pass, making it structurally superior to Bubble Sort if you are working on old flash memory hardware where writing to memory is drastically more expensive than reading from it.

Step-By-Step Example

Let’s see how Selection Sort algorithm works on using a array: [7, 3, 9, 2, 6, 4].

Note:

• The | bar separates the sorted section (left) from the unsorted section (right).
• In each pass, we scan the unsorted section to find the minimum, then swap it to the front of that section.

• Step 1: The First Big Scan

Starting array: [7, 3, 9, 2, 6, 4]

We assume the first element (7) is our temporary minimum. Now we scan the rest to find something smaller:

• Compare current min (7) with 3 : Is 3 < 7? Yes -> New tracked min = 3
• Compare current min (3) with 9 : Is 9 < 3? No -> Keep tracked min = 3
• Compare current min (3) with 2 : Is 2 < 3? Yes -> New tracked min = 2
• Compare current min (2) with 6 : Is 6 < 2? No -> Keep tracked min = 2
• Compare current min (2) with 4 : Is 4 < 2? No -> Keep tracked min = 2

End of Pass 1: The scan is complete. The absolute minimum found is 2. We make our one single swap for this pass, exchanging 2 with the first element (7).

Array State : [2 | 3, 9, 7, 6, 4] (The 2 is now locked in place).

• Step 2: Finding the Next Smallest

Active boundary: [3, 9, 7, 6, 4] (We ignore index 0 where 2 is)

We assume the first element of this section (3) is our temporary minimum:

• Compare current min (3) with 9 : Is 9 < 3? No -> Keep tracked min = 3
• Compare current min (3) with 7 : Is 7 < 3? No -> Keep tracked min = 3
• Compare current min (3) with 6 : Is 6 < 3? No -> Keep tracked min = 3
• Compare current min (3) with 4 : Is 4 < 3? No -> Keep tracked min = 3

End of Pass 2: The scan is complete. The absolute minimum in this section is 3. Since it’s already at the front of the active boundary, no actual swap changes its position.

Array State: [2, 3 | 9, 7, 6, 4] (The 3 is now locked in place).

• Step 3: Shrinking the Window

Active boundary: [9, 7, 6, 4] (We now ignore 2 and 3)

We assume the first element of this section (9) is our temporary minimum:

• Compare current min (9) with 7 : Is 7 < 9? Yes -> New tracked min = 7
• Compare current min (7) with 6 : Is 6 < 7? Yes -> New tracked min = 6
• Compare current min (6) with 4 : Is 4 < 6? Yes -> New tracked min = 4

End of Pass 3: The scan is complete. The absolute minimum found is 4. Swap 4 with the first element of this section (9).

Array State: [2, 3, 4 | 7, 6, 9] (The 4 is now locked in place).

• Step 4: Getting Closer

Active boundary: [7, 6, 9]

We assume the first element of this section (7) is our temporary minimum:

• Compare current min (7) with 6 : Is 6 < 7? Yes -> New tracked min = 6
• Compare current min (6) with 9 : Is 9 < 6? No -> Keep tracked min = 6

End of Pass 4: The scan is complete. The absolute minimum found is 6. Swap 6 with the first element of this section (7).

Array State: [2, 3, 4, 6 | 7, 9] (The 6 is now locked in place).

• Step 5: The Final Matchup

Active boundary: [7, 9]

We assume the first element of this section (7) is our temporary minimum:

• Compare current min (7) with 9 : Is 9 < 7? No -> Keep tracked min = 7

End of Pass 5: The scan is complete. The absolute minimum is 7. It is already in place.

• Array State: [2, 3, 4, 6, 7 | 9] (The 7 is now locked in place).

• Step 6: The Last Element standing

Active boundary: [9]

The algorithm looks at the final remaining element. Because an array of size n only requires (n-1) passes to fully organize, the final item (9) is automatically in its correct position by default.

Final Sorted Array: [2, 3, 4, 6, 7, 9]

Following is a program of the general Selection Sorting. (in C++)

#include <iostream>
#include <vector>
#include <utility> // Required for std::swap

void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    
    // Outer loop: shifts the boundary of the sorted section
    for (int i = 0; i < n - 1; i++) {
        // Assume the current first element of the unsorted section is the minimum
        int minIndex = i;
        
        // Inner loop: scans the remaining unsorted elements to find the true minimum
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // Update index of the smallest element found
            }
        }
        
        // Optimization: Only swap if a smaller element was actually found
        if (minIndex != i) {
            std::swap(arr[i], arr[minIndex]);
        }
    }
}

// Helper function to print the vector layout
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << "\n";
}

int main() {
    // Using the 6-digit array from our walkthrough example
    std::vector<int> numbers = {7, 3, 9, 2, 6, 4 };
    
    std::cout << "Original Array: ";
    printVector(numbers);
    
    selectionSort(numbers);
    
    std::cout << "Sorted Array:   ";
    printVector(numbers);
    
    return 0;
}

Just like with Bubble Sort, switching your Selection Sort from ascending (smallest to largest) to descending order (largest to smallest) requires changing one single character in your code logic.

The updated code in Descending order will be:

void selectionSortDescending(std::vector<int>& arr) {
    int n = arr.size();
    
    // Outer loop: shifts the boundary of the sorted section
    for (int i = 0; i < n - 1; i++) {
        // Assume the current first element is the largest (maximum)
        int maxIndex = i;
        
        // Inner loop: scans the remaining elements to find the true maximum
        for (int j = i + 1; j < n; j++) {
            // FLIPPED: Change '<' to '>' to find the largest remaining number
            if (arr[j] > arr[maxIndex]) {
                maxIndex = j; // Update index of the largest element found
            }
        }
        
        // Only swap if a larger element was actually found down the line
        if (maxIndex != i) {
            std::swap(arr[i], arr[maxIndex]);
        }
    }
}

How is it different from Bubble Sort?

Feature/Trait	Bubble Sort	Selection Sort
Core Concept	Consistently compares and swaps adjacent elements if they are out of order, forcing values to drift to the end.	Scans the entire remaining array to find the absolute minimum value, then drops it into place with a single swap.
Number of Swaps	High (O($n^2$)): Continuous swapping throughout every pass. Memory-heavy on writes.	Low (O(n)): Performs at most (n – 1) total swaps (maximum 1 swap per pass). Excellent for low-write memory.
Algorithm Stability	Stable: Identical elements retain their original relative positioning because adjacent elements are only swapped if one is strictly greater/less than the other.	Unstable: Long-distance swaps can easily bypass identical elements, destroying their original order.
Adaptive Optimization	Highly Adaptive: Can be optimized with a swapped flag to exit early if the array becomes sorted mid-execution, giving it a Best-Case Time Complexity of O(n).	Non-Adaptive: Cannot look ahead or stop early. It is blindly forced to run all passes and comparisons regardless of whether the array is already sorted, keeping its Best Case at O($n^2$)
Time Complexity	Best: O(n) (Optimized) Avg: O($n^2$) Worst: O($n^2$)	Best: O($n^2$) Avg: O($n^2$) Worst: O($n^2$)
Space Complexity	O(1) (In-place)	O(1) (In-place)

Selection Sort introduces a completely different philosophy to basic sorting. While it shares the exact same O($n^2$) time complexity as Bubble Sort, it replaces chaotic, adjacent swapping with a patient, scanning approach—making only one decisive move per pass.

Although it isn’t designed for massive datasets, its strict constraint of a maximum of (n-1) swaps makes it highly efficient for specialized hardware where reducing memory writes is critical.