Day 56 - Sorting Algorithms (Bubble, Selection, Insertion)

📅 Date: Jan 19, 2026

🧠 Mood: Order out of Chaos 📊

🔥 Topic: DSA: Sorting Algorithms (Selection & Bubble Sort)

🧹 Why Sorting?

Imagine finding a word in a dictionary where the words are NOT in alphabetical order. Nightmare, right? Sorting is the process of arranging data in a specific format (Ascending or Descending). Today, I will cover two fundamental sorting techniques.

---

🎯 1. Selection Sort

Analogy: Look at all the cards in your hand. Find the absolute smallest card, pull it out, and put it at the very front. Repeat for the remaining cards.

Time Complexity: O(N²) - because we use nested loops.

Space Complexity: O(1) - we sort it in place.

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr, int n) {
    for(int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find the minimum element in the unsorted array
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap the found minimum with the first element
        swap(arr[minIndex], arr[i]);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr, arr.size());
    
    cout << "Sorted array: ";
    for(int i : arr) cout << i << " ";
    return 0;
}

---

🫧 2. Bubble Sort

Analogy: Think of underwater bubbles. The heaviest elements sink to the bottom (end of the array), and the lighter ones float up. We compare adjacent elements and swap them if they are in the wrong order.

Time Complexity: O(N²) in worst case. O(N) in best case (if already sorted and optimized).

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr, int n) {
    for(int i = 1; i < n; i++) {
        // For round 1 to n-1
        bool swapped = false;
        
        for(int j = 0; j < n - i; j++) {
            // Process elements till n-i 
            if(arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        
        // Optimization: If no two elements were swapped, array is sorted!
        if(swapped == false) {
            break;
        }
    }
}

int main() {
    vector<int> arr = {10, 1, 7, 6, 14, 9};
    bubbleSort(arr, arr.size());
    
    cout << "Sorted array: ";
    for(int i : arr) cout << i << " ";
    return 0;
}

---

🚀 Day 56 Challenge

1. Take a piece of paper, write the array {5, 3, 8, 4, 2} and do a manual Dry Run of both algorithms.
2. Research about Insertion Sort. How is it different from these two? I will cover it in the next post.

Next Up: Day 57 - Insertion Sort & C++ STL Sort function.