Bubble sort explained step by step (C, C++ and Python)

Bubble sort puts a list in order by looking at two neighbours at a time. If the left one is bigger, they swap. That is the whole rule. Repeat it from left to right enough times and the list ends up sorted.

It is the first sorting algorithm most students meet, and it is slow on big lists. It is still worth learning properly, because nearly every idea in sorting shows up in it in miniature: comparisons, swaps, passes, the best and worst case, and why some algorithms beat others.

The one rule, and why it is called "bubble"

Look at positions 0 and 1. If a[0] > a[1], swap them. Then look at positions 1 and 2, then 2 and 3, all the way to the end. One trip from left to right is called a pass.

Watch what happens to the biggest number during a pass. Wherever it starts, once the pass reaches it, it is bigger than its right-hand neighbour, so it swaps. Then it is compared again, swaps again, and keeps moving right until it reaches the end. It rises through the list like a bubble through water. That gives bubble sort its name and its key fact:

After pass 1, the largest value is in its final place. After pass 2, the two largest are. After pass k, the last k places are finished.

So each pass can stop one place earlier than the one before.

A worked example, pass by pass

Sort [5, 3, 8, 4, 2].

Pass 1 (compare positions 0–1, 1–2, 2–3, 3–4):

Compare	Result	List after
5 and 3	5 > 3, swap	3, 5, 8, 4, 2
5 and 8	keep	3, 5, 8, 4, 2
8 and 4	8 > 4, swap	3, 5, 4, 8, 2
8 and 2	8 > 2, swap	3, 5, 4, 2, 8

8 has bubbled to the end. It never needs to be looked at again.

Pass 2 (only the first four places):

Compare	Result	List after
3 and 5	keep	3, 5, 4, 2, 8
5 and 4	swap	3, 4, 5, 2, 8
5 and 2	swap	3, 4, 2, 5, 8

Pass 3: 3 and 4 keep, 4 and 2 swap → 3, 2, 4, 5, 8.

Pass 4: 3 and 2 swap → 2, 3, 4, 5, 8. Sorted.

Count the work: 4 + 3 + 2 + 1 = 10 comparisons and 7 swaps. The 7 is not a coincidence. It is the number of pairs in the original list that were in the wrong order (5 before 3, 5 before 4, 5 before 2, 3 before 2, 8 before 4, 8 before 2, 4 before 2). Each swap of two neighbours fixes exactly one such pair, so bubble sort always makes exactly that many swaps.

Stopping early: the swapped flag

What if the list is almost sorted already? Take [1, 2, 4, 3, 5].

Pass 1 finds one pair out of order (4 and 3), swaps it, and the list is [1, 2, 3, 4, 5]. Pass 2 compares 1–2, 2–3 and 3–4 and swaps nothing.

A pass with no swaps proves every neighbour is in order, which means the whole list is sorted. So we keep a flag, swapped, that starts each pass as false and turns true on any swap. If it is still false at the end of a pass, we stop. Here that saves two passes: 7 comparisons instead of 10.

The code in C, C++ and Python

These are the same listings used in the Ordo course. Each one is compiled and run against a test before it goes into the course.

C

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++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

C++

void bubbleSort(vector<int>& a) {
    int n = a.size();
    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;
    }
}

Python

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break

Reading it line by line:

• The outer loop (i) counts passes. A list of n items needs at most n − 1 passes, because once n − 1 values are in their final places, the last one has nowhere else to be.
• The inner loop (j) walks the pairs a[j] and a[j + 1]. It stops at n - 1 - i: the - 1 keeps a[j + 1] inside the array, and the - i skips the last i places, which earlier passes have already finished.
• The comparison a[j] > a[j + 1] is the whole rule. The swap is three lines in C, swap() in C++, and one tuple assignment in Python.
• swapped is reset at the start of every pass and checked at the end.

How much work it does

Count comparisons, because that is what the inner loop does every time.

Input	Passes	Comparisons	Swaps
Already sorted	1	n − 1	0
Random order	about n − 1	close to n(n − 1)/2	about n(n − 1)/4 on average
Reversed	n − 1	n(n − 1)/2	n(n − 1)/2

For 5 items, n(n − 1)/2 is 10, as in the example above. For 1,000 items it is 499,500. Doubling the list roughly quadruples the work, which is what O(n²) means. The best case, a list that is already sorted, takes one pass and is O(n), thanks to the flag.

Two more properties are worth knowing for exams:

• In place. It only needs one spare variable for the swap, so the extra memory is O(1).
• Stable. Equal values never swap, because the test is > and not >=. So two students with the same mark stay in their original order.

Mistakes beginners make

1. Running the inner loop to n instead of n - 1. On the last step a[j + 1] reads one past the end of the array. In C this is undefined behaviour; in Python it raises IndexError.
2. Forgetting the - i. The sort still works, but every pass re-checks the finished end of the list. It does more comparisons for nothing.
3. Writing >= instead of >. Equal neighbours now swap. The result is still sorted, but the sort is no longer stable and makes extra swaps.
4. Setting swapped = false once, outside the outer loop. After the first swap it stays true forever, so the early stop never happens.
5. Thinking one pass sorts the list. One pass only guarantees that the largest value is at the end. In the example above, the list after pass 1 is 3, 5, 4, 2, 8, which is far from sorted.

When would you actually use it?

Mostly to learn. For real programs, use your language's built-in sort (sorted() or list.sort() in Python, std::sort in C++, qsort in C), which is far faster on large inputs. Among the simple O(n²) sorts, insertion sort is usually the better choice for small or nearly sorted lists, and merge sort and quick sort are the standard O(n log n) algorithms you meet next.

Bubble sort's real value is that it makes the cost of sorting visible. Once you have counted its 10 comparisons on 5 items, the question "can we do better than n²?" makes sense, and the faster sorts are the answers to it.

Check yourself

1. How many comparisons does bubble sort make on [4, 3, 2, 1]? Answer: 3 + 2 + 1 = 6. The list is reversed, so no pass can stop early. It makes 6 swaps too.
2. After pass 2 of any bubble sort, which positions are guaranteed to be final? Answer: the last two. Each pass places the largest of the values that are not yet finished.
3. Why does a pass with no swaps mean the list is sorted? Answer: the pass compared every neighbouring pair in the unfinished part and found each one in order, and the finished part was already in place. A list whose neighbours are all in order is sorted.

In the bubble sort scene of Ordo, our data structures and algorithms course, you start with the row 8, 3, 4, 2, 7, 1, 6, 5 and decide each pair yourself, Swap or Keep, until the 8 reaches the end. Then you step through the real code, with the running line lit in C, C++ or Python, and try a reversed row and a sorted one to see the worst and best case.