1
🫧 Bubble Sort — Float the Largest to the End Each Pass
Repeatedly compare adjacent pairs and swap if out of order — largest element settles at the end of each pass
O(n²) / stable
Bubble Sort scans the array from left to right, compares each pair of adjacent elements, and swaps them if they are in the wrong order. After one full pass, the largest unsorted element has bubbled to its final position at the end. The next pass works on one fewer element, and so on. We use an optimised version with an early-exit flag: if a complete pass produces zero swaps, the array is already sorted and we stop immediately — turning the best case into O(n). Worst case remains O(n²). Space: O(1). It is stable because we swap only when
arr[j] > arr[j+1] — equal elements never swap.
#include <stdio.h> void printArr(const char *label, int *a, int n) { printf(" %-18s [ ", label); for (int i = 0; i < n; i++) printf("%3d ", a[i]); printf("]\n"); } void bubbleSort(int *arr, int n) { int totalSwaps = 0; for (int pass = 1; pass < n; pass++) { int swapped = 0; /* early-exit flag */ for (int j = 0; j < n - pass; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; swapped++; totalSwaps++; } } /* Print the array after this pass */ char label[32]; sprintf(label, "Pass %d (%d swap%s)", pass, swapped, swapped == 1 ? "" : "s"); printArr(label, arr, n); if (!swapped) { printf(" *** No swaps — array already sorted! ***\n"); break; /* early exit O(n) best case */ } } printf("\n Total swaps : %d\n", totalSwaps); } int main() { int arr[] = { 64, 25, 12, 90, 43, 8, 55, 37 }; int n = sizeof(arr) / sizeof(arr[0]); printf("=== Bubble Sort ===\n"); printArr("Input", arr, n); printf("\n After each pass (largest element fixed at right end):\n"); printf(" %s\n", "----------------------------------------------"); bubbleSort(arr, n); printf("\n"); printArr("Sorted", arr, n); return 0; }
=== Bubble Sort === Input [ 64 25 12 90 43 8 55 37 ] After each pass (largest element fixed at right end): ---------------------------------------------- Pass 1 (6 swaps) [ 25 12 64 43 8 55 37 90 ] Pass 2 (5 swaps) [ 12 25 43 8 55 37 64 90 ] Pass 3 (4 swaps) [ 12 25 8 43 37 55 64 90 ] Pass 4 (3 swaps) [ 12 8 25 37 43 55 64 90 ] Pass 5 (2 swaps) [ 8 12 25 37 43 55 64 90 ] Pass 6 (0 swaps) [ 8 12 25 37 43 55 64 90 ] *** No swaps — array already sorted! *** Total swaps : 20 Sorted [ 8 12 25 37 43 55 64 90 ]
pass-by-pass trace — one more element locks into place from the right each pass
Input
64
25
12
90
43
8
55
37
← unsorted
After pass 1
25
12
64
43
8
55
37
90
← 90 settled
After pass 2
12
25
43
8
55
37
64
90
← 64 settled
After pass 4
12
8
25
37
43
55
64
90
← growing sorted suffix
After pass 5
8
12
25
37
43
55
64
90
← sorted! pass 6 exits early
The early-exit optimisation is essential. Without it, Bubble Sort always runs all n-1 passes even if the array sorted itself on pass 2. Adding the
swapped flag makes the best case O(n) — just one pass to confirm nothing needs swapping. Always include it in any real implementation of Bubble Sort.After pass k, the k largest elements are permanently settled in their correct positions at the right end. This is why the inner loop shrinks by one each pass —
j < n - pass — there is no point comparing elements that are already in their final position. This reduces the total comparison count from n² to n(n-1)/2.
example 2
2
🔍 Selection Sort — Find the Minimum and Place It
Scan for the smallest unsorted element and swap it to its correct position — exactly n-1 swaps total
O(n²) / in-place
Selection Sort divides the array into a sorted prefix (left) and an unsorted suffix (right). Each pass scans the entire unsorted suffix to find the index of the minimum element, then swaps it with the first unsorted position. The sorted prefix grows by one each pass. Unlike Bubble Sort, Selection Sort makes exactly n-1 swaps — regardless of input order — because it only swaps once per pass. This makes it preferable when writes are expensive (e.g. flash memory). Time: O(n²) always. Space: O(1). It is not stable by default because the swap can move an element past its equal partner.
#include <stdio.h> void printArr(const char *label, int *a, int n, int sortedUpto) { printf(" %-20s [ ", label); for (int i = 0; i < n; i++) { if (i <= sortedUpto) printf("\e[32m%3d\e[0m ", a[i]); /* green = sorted */ else printf("%3d ", a[i]); } printf("]\n"); } void selectionSort(int *arr, int n) { for (int i = 0; i < n - 1; i++) { /* Find index of minimum in arr[i..n-1] */ int minIdx = i; for (int j = i + 1; j < n; j++) if (arr[j] < arr[minIdx]) minIdx = j; /* Swap minimum into position i */ if (minIdx != i) { int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } /* Trace: show what was found and placed */ char label[48]; sprintf(label, "Pass %d min=%d@[%d]", i + 1, arr[i], minIdx); printArr(label, arr, n, i); } } int main() { int arr[] = { 29, 10, 72, 13, 50, 7, 61, 35 }; int n = sizeof(arr) / sizeof(arr[0]); printf("=== Selection Sort ===\n"); printArr("Input", arr, n, -1); printf("\n Each pass: scan suffix, swap minimum to front of suffix\n"); printf(" %s\n", "-----------------------------------------------------"); selectionSort(arr, n); printf("\n"); printArr("Sorted", arr, n, n - 1); printf("\n Total swaps: exactly %d (= n - 1)\n", n - 1); return 0; }
=== Selection Sort === Input [ 29 10 72 13 50 7 61 35 ] Each pass: scan suffix, swap minimum to front of suffix ----------------------------------------------------- Pass 1 min=7@[5] [ 7 10 72 13 50 29 61 35 ] Pass 2 min=10@[1] [ 7 10 72 13 50 29 61 35 ] Pass 3 min=13@[3] [ 7 10 13 72 50 29 61 35 ] Pass 4 min=29@[5] [ 7 10 13 29 50 72 61 35 ] Pass 5 min=35@[7] [ 7 10 13 29 35 72 61 50 ] Pass 6 min=50@[7] [ 7 10 13 29 35 50 61 72 ] Pass 7 min=61@[6] [ 7 10 13 29 35 50 61 72 ] Sorted [ 7 10 13 29 35 50 61 72 ] Total swaps: exactly 7 (= n - 1)
pass-by-pass trace — sorted prefix grows from left, each pass costs exactly 1 swap
Input
29
10
72
13
50
7
61
35
← min=7 found at [5]
After pass 1
7
10
72
13
50
29
61
35
← 7 placed, swapped with 29
After pass 3
7
10
13
72
50
29
61
35
← 3 placed, 5 remain
After pass 5
7
10
13
29
35
72
61
50
← 5 placed, 3 remain
Done
7
10
13
29
35
50
61
72
← fully sorted
Selection Sort always makes exactly n-1 swaps — one per pass — regardless of the input order. Bubble Sort on the same input made 20 swaps. This makes Selection Sort attractive when the cost of writing data is much higher than the cost of reading it, such as writing to EEPROM or flash storage where write cycles are limited and expensive.
Selection Sort is not stable by default. When the minimum element is swapped into position, it can jump over an equal element, breaking their original relative order. For example, with
[5a, 5b, 1], pass 1 swaps 1 with 5a giving [1, 5b, 5a] — 5a and 5b are now reversed. A stable variant exists (shift instead of swap) but adds O(n) writes per pass, removing the write-count advantage.side-by-side comparison
bubble sort vs selection sort — key differences at a glance
Strategy
Bubble: swap adjacent pairs
Selection: find min, swap once
Swaps (worst)
Bubble: O(n²) swaps
Selection: exactly n-1 swaps
Best case
Bubble: O(n) w/ early exit
Selection: always O(n²)
Stable
Bubble: YES
Selection: NO
Best for
Bubble: nearly sorted data
Selection: minimising writes
checklist
- Bubble Sort — compare adjacent pairs, swap if out of order, repeat. After pass k, k largest elements are locked at the right end. Add a
swappedflag for O(n) best case. Stable. O(n²) worst, O(1) space. - Selection Sort — find the index of the minimum in the unsorted suffix, swap it to position i. Makes exactly n-1 swaps regardless of input. Not stable. O(n²) all cases, O(1) space. Best when writes are expensive.