📅 Date: Jan 17, 2026
🔥 Topic: Sorting Part 2: Selection Sort

🎯 The Logic

Selection Sort is different. Instead of swapping constantly, it scans the list to find the Minimum element and puts it at the beginning.

📊 Dry Run Table

Let's sort: [64, 25, 12, 22, 11]

Pass Min Found Swap Action Array State
1 11 Swap 11 with 64 [11, 25, 12, 22, 64]
2 12 Swap 12 with 25 [11, 12, 25, 22, 64]
3 22 Swap 22 with 25 [11, 12, 22, 25, 64]

💻 The Code (O(n²))

#include <iostream>
using namespace std;

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;

    for(int i = 0; i < n-1; i++) {
        int minIndex = i; // Assume current is min
        
        // Find actual min in remaining array
        for(int j = i+1; j < n; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // Swap the found min with current position
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }

    for(int i=0; i<n; i++) cout << arr[i] << " ";
    return 0;
}

💭 Thoughts

Selection sort makes fewer swaps compared to Bubble Sort, but the time complexity is still O(n²) because of the nested loops.