DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).
Exchange (Bubble) Sort
Compare adjacent pairs and swap the ones out of order — the simplest sort to write, and the one worth understanding precisely because of what it costs.
How it works
Walk the list comparing each element with its neighbour, swapping whenever they are out of order. After one full pass the largest element has been carried to the end — it cannot be overtaken, because every comparison it wins moves it one place further right.
Worked example — bubble sort on [5, 2, 4, 1]:
start 5 2 4 1
pass 1 2 4 1 5 5 has bubbled to the end
pass 2 2 1 4 5 4 is now in place
pass 3 1 2 4 5 sorted
After pass k, the last k elements are final —
so each pass can be one comparison shorter than the last.
That shrinking range is why the comparison count is roughly n²/2 rather than n². The first pass makes n−1 comparisons, the second n−2, and so on — the sum of which is n(n−1)/2. Being able to derive that, rather than quoting O(n²), is what an examiner is checking.
Why it is O(n²), and when it is not
Comparisons: (n−1) + (n−2) + … + 1 = n(n−1)/2 → O(n²)
Worst case reverse-sorted input
every comparison swaps: O(n²) swaps too
Average O(n²)
Best case ALREADY SORTED, with the early-exit check
→ one pass, no swaps → O(n)
The early exit: if a full pass makes no swaps, the list is
sorted and the algorithm can stop. Without that check,
bubble sort is O(n²) even on sorted input.
💡 The best case is the trap. Bubble sort is O(n) on already-sorted data only if the implementation tracks whether a pass made any swaps. A question asking "what is the best-case complexity of bubble sort" is really asking whether you know about that flag — and the answer differs depending on whether it is present.
Why it is not used in practice
It is O(n²) on realistic input, and it moves elements one position at a time — the slowest possible way to correct a large displacement. An element that belongs at the far end takes an entire pass per position it must travel.
Insertion sort has the same worst-case complexity and beats it consistently, because it does not repeatedly re-scan the sorted portion. Bubble sort survives in teaching, not in libraries.
🔧 It does have one genuine property: it is stable, meaning equal elements keep their original relative order, because it only ever swaps strictly out-of-order neighbours. That matters when sorting records by one field after already sorting by another — and it is the kind of detail that distinguishes a full answer from a partial one.
Commonly confused
Bubble and selection sort. Bubble swaps adjacent pairs repeatedly. Selection scans for the minimum and places it with one swap per pass — far fewer swaps, same comparison count.
Best case O(n) unconditionally. Only with the swap-detection flag.
Stable meaning fast. Stability is about preserving order among equals, not about speed.
Rapid revision
Adjacent compare-and-swap; after pass k the last k are final.
n(n−1)/2 comparisons → O(n²), worst and average.
O(n) best case only with an early-exit flag.
Stable, because only strictly out-of-order neighbours are swapped.
Syllabus points
Bubble sort mechanism
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.