# 3.2 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.

Chapter: Simple Sorting & Searching · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/bubble-sort

## Mental 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.

## C++ code: bubble-sort.cpp

```cpp
#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);
}
```

Expected output:

```text
Before: 29 10 14 37 13 5
After:  5 10 13 14 29 37
```

## Complexity

| Case | Cost |
| --- | --- |
| 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 |

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.

## Videos

- [Bubble sort algorithm](https://youtu.be/Jdtq5uKz-w4) (mycodeschool): Slow and careful. Traces every comparison and builds the C code with you.
- [Bubble sort in 2 minutes](https://youtu.be/xli_FI7CuzA) (Michael Sambol): A 2-minute visual recap. Watch it right before an exam.

## Exam 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 `swapped` flag? 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 `j` up to `n - 1` in every pass instead of `n - 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 < n` and then accessing `a[j + 1]`.
- Forgetting to reset `swapped = false` at the start of each pass.

## Quick check

1. After the **first** pass of bubble sort on `4, 3, 2, 1`, the array is:
   A. `3, 2, 1, 4`
   B. `1, 2, 3, 4`
   C. `3, 4, 2, 1`
   D. `1, 4, 3, 2`
   Answer: A. The 4 bubbles all the way to the end. The rest moves left by one place each.

2. What is the best-case time complexity of bubble sort **with** the early-exit flag?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. On sorted input the first pass makes n−1 comparisons, no swaps, and stops.

3. Which change makes bubble sort **unstable**?
   A. Using `>=` instead of `>`
   B. Removing the `swapped` flag
   C. Looping `i` from `n-1` down to 1
   D. Using `std::swap`
   Answer: A. With `>=`, two equal items get swapped, so their original order is lost.

4. How many comparisons does bubble sort make on 6 items in the worst case?
   A. 6
   B. 15
   C. 30
   D. 36
   Answer: B. n(n−1)/2 = 6·5/2 = 15.

## Practice

**Trace by hand.** Trace bubble sort on `5, 1, 4, 2, 8`. Write the array after every pass and count the swaps.

Solution:

- 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`).

```cpp
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";
}
```


**Problems:**

- [Sort an Array (try bubble sort first, see it time out)](https://leetcode.com/problems/sort-an-array/) (medium). 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.
- [Move Zeroes](https://leetcode.com/problems/move-zeroes/) (easy). Hint: Think of zeros as "heavy" items that must sink to the end, like bubble sort, but you can do it in one pass.
- [Bubble Sort (HackerRank)](https://www.hackerrank.com/challenges/ctci-bubble-sort/problem) (easy). Hint: Count every swap while sorting, then print the count, first and last element.

## Mastery checklist

- [ ] I can trace bubble sort pass by pass on a small array.
- [ ] I can write bubble sort from memory, including the swapped flag.
- [ ] I can explain why the best case is O(n) and the worst case is O(n²).
- [ ] I can explain why bubble sort is stable.