Bubble sort

Prerequisites

• Arrays and zero-based indexing.
• Nested loops and how to count their iterations.
• Big-O notation (see Complexity analysis).

The analogy

How it works

Start with one pass by hand

Take [5, 1, 4, 2] and compare neighbours from left to right. At each step, guess first, then open "Check".

Finish the run

The 5 is done, so pass 2 only looks at [1, 4, 2].

• Pass 2. Predict: which pair swaps?
  Check

  1 and 4 stay. 4 and 2 swap: [1, 2, 4, 5].

• Pass 3. Only 1, 2 are left to compare. Predict: does anything swap?
  Check

  No. A pass with no swaps means we stop. Total: 6 comparisons, 4 swaps.

The rule in plain words

Compare two neighbours. If the left is bigger, swap. Move one step right. Repeat until the end of the array. That is one pass.

Do passes until one makes no swaps. Each pass can stop one place earlier, because the end is already finished.

The code

Read this code after you have done one pass by hand. It will make more sense.

void bubble_sort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {   /* last i items are final */
            if (a[j] > a[j + 1]) {               /* strict > keeps it stable */
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;                     /* no swaps: already sorted */
    }
}

flowchart TD
  A["Start a pass: swapped = false"] --> B{"a[j] > a[j+1] ?"}
  B -->|yes| C["Swap them, swapped = true"]
  B -->|no| D["Move j one step right"]
  C --> D
  D --> E{"End of the unsorted part?"}
  E -->|no| B
  E -->|yes| F{"swapped?"}
  F -->|yes| A
  F -->|no| G["Done: the array is sorted"]
          

How fast is it?

In the worst case (reversed input), the passes make $n-1$, then $n-2$, … then $1$ comparisons. Adding them up:

Each swap fixes exactly one inversion, a pair with $i < j$ and $a_i > a_j$. So the number of swaps equals the number of inversions. In our example that was 4.

Common mistakes

• Forgetting the swapped flag, so sorted input still costs $O(n^2)$.
• Running j up to n - 1, which reads a[n] out of bounds, instead of stopping at n - 1 - i.
• Swapping on >= instead of >, which moves equal items past each other and breaks stability.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• After pass $k$, the $k$ largest values are final, because each pass carries the largest remaining value all the way to the end.
• The worst case is $O(n^2)$ because there are up to $n-1$ passes, and together they make $\frac{n(n-1)}{2}$ comparisons.
• The best case is $O(n)$ because, with the flag, a sorted array needs just one pass with no swaps.
• The number of swaps equals the number of inversions because each neighbour swap fixes exactly one out-of-order pair.
• It is stable because it swaps only on a strict $>$, so equal values never pass each other.
• Extra space is $O(1)$ because it only swaps inside the array, using one temporary variable.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. Why is it called "bubble" sort?
   Sample answer

   Like bubbles rising in a soda, the largest values move toward the end one swap at a time.

2. Walk through the first pass on [5, 1, 4, 2]. What is guaranteed at the end of it?
   Sample answer

   5 swaps with 1, then with 4, then with 2, giving [1, 4, 2, 5]. The largest element is now in its final position, so the next pass can ignore it.

3. Looking at the code: is bubble sort stable and in-place? Which detail makes it stable?
   Sample answer

   Yes to both. The strict > means equal neighbours are never swapped, so equal items never pass each other, and it needs only one temporary variable.

4. So what is bubble sort, in one sentence?
   Sample answer

   It repeatedly compares neighbouring elements and swaps them when they're out of order, until a full pass makes no swaps.

5. When does the algorithm stop early?
   Sample answer

   When a whole pass makes no swaps: every neighbour pair is in order, so the array is sorted.

6. Why does bubble sort have an $O(n)$ best case only when it uses an early-stop flag?

   A good answer says what happens to the passes without the flag.

   Sample answer

   Without the flag it always runs all $n-1$ passes, so it can't notice that the array is already sorted. The flag is an $O(1)$ check that ends the loop after one pass with no swaps.

7. What is its time and space complexity?
   Sample answer

   $O(n^2)$ in the worst and average case, $O(n)$ in the best case on sorted input with the early-stop flag. Extra space is $O(1)$.

8. Why is the number of swaps exactly the number of inversions?

   A good answer says which pairs a single swap affects.

   Sample answer

   Swapping two out-of-order neighbours fixes that one pair and leaves the order of every other pair unchanged. So each swap removes exactly one inversion, and sorting ends when none are left.

9. Why would you pick insertion sort over bubble sort in practice?
   Sample answer

   Both are $O(n^2)$ and $O(n)$ on sorted input, but insertion sort shifts items instead of doing full three-step swaps, so it does fewer writes and runs faster. Bubble sort is mainly a teaching tool.

10. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
    Sample answer

    I'd leave out the inversion count and the exact $\frac{n(n-1)}{2}$ formula, and keep one pass on a small array, the rule, the stop condition and "$O(n^2)$, stable, in-place". A beginner needs the picture and the takeaway, not the proof.

External resources

• VisuAlgo: Sorting: step through bubble sort on your own input.
• Toptal: Bubble sort animation: watch it race on random, nearly sorted and reversed data.
• GeeksforGeeks: Bubble sort: an article with code in several languages.
• Wikipedia: Bubble sort: history, analysis and variants such as cocktail shaker sort.

Videos

• YouTube: bubble sort as a Hungarian folk dance: the famous AlgoRythmics video, a fun way to remember the swaps.
• YouTube search: bubble sort explained: pick a short walkthrough of a full run.