Bubble Sort in C++
In this lesson: Bubble sort algorithm in C++ — logic, pass-by-pass dry run, optimized version and output. Copy & run. In Hindi & English.
Bubble Sort Concept and Loop Invariant
Bubble sort scans adjacent pairs, swaps a pair that is out of order, and repeats passes until no disorder remains. After one complete ascending pass, the largest element in the active range is at its final position. That statement is the pass invariant and explains why the next pass can ignore the sorted suffix.
For ascending order, compare values[i] with values[i+1]; swap only when the first is greater. Each swap removes at least one adjacent inversion.
The result must be ordered and must contain exactly the original elements. This is more important than merely producing the expected output for one example. Compare this elementary method with selection and insertion sort.
Pass-by-Pass Trace
Sort {5, 1, 4, 2, 8} in ascending order:
| Pass | Important swaps | Sequence after pass | Fixed suffix |
|---|---|---|---|
| 1 | 5↔1, 5↔4, 5↔2 | 1 4 2 5 8 | 8 |
| 2 | 4↔2 | 1 2 4 5 8 | 5 8 |
| 3 | None | 1 2 4 5 8 | Whole range sorted |
The third pass makes no swap, so an optimized implementation stops. Without early exit, the output is still correct but needless comparisons continue.
Algorithm and Pseudocode
for end = size down to 2
swapped = false
for i = 0 while i + 1 < end
if values[i] > values[i + 1]
swap the two values
swapped = true
if swapped is false
stop| Compare | Pair | Swap? | Array ab |
|---|---|---|---|
| i=0,1 | 5, 1 | haan | 1, 5, 4, 2 |
| i=1,2 | 5, 4 | haan | 1, 4, 5, 2 |
| i=2,3 | 5, 2 | haan | 1, 4, 2, 5 |
| Pehla pass poora — 5 (sabse bada) end me. Agle pass: 1,2,4,5 (sorted). swapped=false hua to loop jaldi ruk jaata hai. | |||
Bubble sort paas wale do numbers compare karke bade ko aage bhejta hai. Har pass me ek bada number sahi jagah pahunch jaata hai. Agar kisi pass me koi swap na ho (swapped=false), matlab array sort ho chuka — loop wahin ruk jaata hai.
end is exclusive. After a pass, values[end-1] is final, so decreasing end is safe. Empty and one-element ranges require no special branch because the outer loop does not run.
Complete Optimized Bubble Sort Program
#include <iostream>
#include <utility>
#include <vector>
void bubble_sort(std::vector<int>& values) {
for (std::size_t end = values.size(); end > 1; --end) {
bool swapped = false;
for (std::size_t i = 0; i + 1 < end; ++i) {
if (values[i] > values[i + 1]) {
std::swap(values[i], values[i + 1]);
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
int main() {
std::vector<int> values{5, 1, 4, 2, 8};
bubble_sort(values);
std::cout << "Sorted:";
for (int value : values) {
std::cout << ' ' << value;
}
std::cout << '\n';
}The function accepts the vector by non-const reference because it intentionally modifies the caller's data. std::size_t matches container sizes, and the end > 1 guard avoids unsigned underflow.
Early Exit and Last-Swap Optimization
The swapped flag changes the best case from quadratic work to one linear pass. A further refinement remembers the position of the last swap: everything after that position was already ordered, so the next active range can end there.
std::size_t end = values.size();
while (end > 1) {
std::size_t last_swap = 0;
for (std::size_t i = 1; i < end; ++i) {
if (values[i - 1] > values[i]) {
std::swap(values[i - 1], values[i]);
last_swap = i;
}
}
end = last_swap;
}This can reduce comparisons on partially sorted data, but it does not change the Θ(n²) average and worst-case growth.
Complexity, Stability and Correctness
| Property | Optimized bubble sort |
|---|---|
| Best time | Θ(n), already sorted |
| Average time | Θ(n²) |
| Worst time | Θ(n²), reverse-like order |
| Auxiliary space | O(1) |
| Stable | Yes with strict > comparison |
| Adaptive | Yes, with early exit |
Correctness follows from two facts: each pass fixes the largest active element, and swaps preserve the multiset of input values. When a pass makes no swap, every adjacent pair is nondecreasing; by transitivity, the whole range is sorted.
When to Use Bubble Sort
Bubble sort is valuable for visualizing invariants, swaps, stability and asymptotic analysis. It may be acceptable for a tiny range, a classroom demonstration, or code where adjacent exchanges are the exact subject being studied. It is a poor default for large arrays.
| Need | Better choice |
|---|---|
| General fast in-memory sorting | std::sort |
| Preserve equivalent-element order | std::stable_sort |
| Predictable Θ(n log n) teaching algorithm | Merge sort |
| Small/nearly sorted sequence | Insertion sort is often more practical |
Also study the STL algorithms guide before writing a custom production sorter.
Common Mistakes, Tests and Practice
| Mistake | Correction |
|---|---|
Inner loop reaches i == end-1 | Require i+1 < end |
Resetting swapped inside inner loop | Reset once per pass |
Using >= | Use strict > to retain stability |
| Unsigned loop decrements below zero | Use an explicit end > 1 condition |
| Claiming O(n) without early exit | State which implementation is analyzed |
Test set: empty, one element, sorted, reverse sorted, all equal, duplicates, negative values and a large random range. Practice: count comparisons and swaps; implement descending order; implement the last-swap boundary; verify stability using records with equal keys.
Authoritative References
The definition, complexity classification and standard-library comparison were checked against these sources. Continue with sorting and searching in C++.
