Bubble Sort
Compare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
Imagine bubbles in a glass of water: the big ones rise to the top. Bubble sort walks along the array comparing each pair of neighbours. If the left one is bigger, they swap. By the end of one pass, the largest item has floated to the last position, and it never moves again.
So each pass fixes one more item at the end:
- Pass 1 puts the largest item in the last slot.
- Pass 2 puts the second largest in the second-to-last slot.
- …and after n − 1 passes, everything is in place.
The early-exit trick
If a whole pass makes no swaps, every neighbour pair is already in order, so the whole array is sorted. The swapped flag lets us stop right there. That is the “avoid late loop termination” idea from Chapter 2, put into practice.
Why the inner loop shrinks
After pass i, the last i items are final. So the inner loop only needs to go up to n - 1 - i. Comparing against the finished part is wasted work.
Bubble sort is rarely used in real programs, but it is the easiest sort to reason about and a favourite for exam traces.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Try the "Sorted" preset to see the early exit, then "Reversed" for the worst case.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <utility>
using namespace std;
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swapped = true;
}
}
if (!swapped) break; // no swaps: already sorted
}
}
void print(const int a[], int n) {
for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
}
int main() {
int a[] = {29, 10, 14, 37, 13, 5};
int n = sizeof(a) / sizeof(a[0]);
cout << "Before: ";
print(a, n);
bubbleSort(a, n);
cout << "After: ";
print(a, n);
}Before: 29 10 14 37 13 5 After: 5 10 13 14 29 37
05Complexity
| Best case (already sorted) | O(n): one pass, no swaps, stop |
|---|---|
| Average case | O(n²) |
| Worst case (reversed) | O(n²): n(n−1)/2 comparisons and swaps |
| Extra space | O(1) |
| Stable? | Yes |
| In-place? | Yes |
The O(n) best case only exists because of the swapped flag. Without it, bubble sort always does n(n−1)/2 comparisons.
06Watch
Bubble sort algorithm
Why this one: Slow and careful. Traces every comparison and builds the C code with you.
Bubble sort in 2 minutes
Why this one: A 2-minute visual recap. Watch it right before an exam.
Original class slides (Python, by the course's lecture authors):Sorting Basics
07Exam lens
Likely questions
- Show every pass of bubble sort on
5, 1, 4, 2, 8. How many swaps happen? - What is the purpose of the
swappedflag? What is the best-case complexity with and without it? - Is bubble sort stable? Explain why using the
>comparison. - How many comparisons does bubble sort make on n items in the worst case?
Common mistakes
- Looping
jup ton - 1in every pass instead ofn - 1 - i. It still works, but does useless comparisons. - Writing
a[j] >= a[j+1]. Swapping equal items breaks stability. - Reading past the array with
j < nand then accessinga[j + 1]. - Forgetting to reset
swapped = falseat the start of each pass.
08Quick check
09Practice
🟢 Trace by hand
Trace bubble sort on 5, 1, 4, 2, 8. Write the array after every pass and count the swaps.
Show answer
- Pass 1:
1 4 2 5 8(3 swaps) - Pass 2:
1 2 4 5 8(1 swap) - Pass 3:
1 2 4 5 8(0 swaps, so stop early)
Total: 4 swaps, 4 + 3 + 2 = 9 comparisons.
🟡 Implement it
Write bubbleSortDesc(int a[], int n) that sorts in descending order, and make it print the number of passes it actually used.
Hint
Flip one comparison. Count passes in the outer loop and print after the loop (or after break).
Solution
void bubbleSortDesc(int a[], int n) {
int passes = 0;
for (int i = 0; i < n - 1; i++) {
passes++;
bool swapped = false;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] < a[j + 1]) { swap(a[j], a[j + 1]); swapped = true; }
if (!swapped) break;
}
cout << "passes: " << passes << "\n";
}🔴 Solve problems
Hint
Bubble sort is correct but O(n²) and will hit the time limit. That is the lesson. Come back after Chapter 8 with merge sort.
Hint
Think of zeros as "heavy" items that must sink to the end, like bubble sort, but you can do it in one pass.
Solution idea
Keep a write index
w. For each non-zerox, writea[w++] = x. Then fill the rest with zeros. O(n).Hint
Count every swap while sorting, then print the count, first and last element.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.