1. Bubble Sort

Algorithm: Compare adjacent elements and swap if they're in wrong order. Repeat until no swaps needed.

Dry Run: [44, 33, 55, 22, 11]

Pass 1:

[44, 33, 55, 22, 11]
 ↑   ↑              Compare 44 & 33 → Swap
[33, 44, 55, 22, 11]
     ↑   ↑          Compare 44 & 55 → No swap
[33, 44, 55, 22, 11]
         ↑   ↑      Compare 55 & 22 → Swap
[33, 44, 22, 55, 11]
             ↑   ↑  Compare 55 & 11 → Swap
[33, 44, 22, 11, 55] ← Largest element bubbled up

Pass 2:

[33, 44, 22, 11, 55]
 ↑   ↑              Compare 33 & 44 → No swap
[33, 44, 22, 11, 55]
     ↑   ↑          Compare 44 & 22 → Swap
[33, 22, 44, 11, 55]
         ↑   ↑      Compare 44 & 11 → Swap
[33, 22, 11, 44, 55] ← Second largest in position

Pass 3:

[33, 22, 11, 44, 55]
 ↑   ↑              Compare 33 & 22 → Swap
[22, 33, 11, 44, 55]
     ↑   ↑          Compare 33 & 11 → Swap
[22, 11, 33, 44, 55] ← Third largest in position

Pass 4:

[22, 11, 33, 44, 55]
 ↑   ↑              Compare 22 & 11 → Swap
[11, 22, 33, 44, 55] ← Array sorted!

Final Sorted Array: [11, 22, 33, 44, 55]

Code:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) { 
        for (int j = 0; j < n - i - 1; j++) { 
            if (arr[j] > arr[j + 1]) {
                // Swap the elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                //same
                //swap(arr[j],arr[j+1]);
            }
        }
    }
}

Time Complexity:

• Best Case: O(n) - When array is already sorted (with optimization)
• Average Case: O(n²) - Random order elements
• Worst Case: O(n²) - When array is reverse sorted

Space Complexity:

• O(1) - Only constant extra space needed for temporary variables