The Bubble Sort Algorithm

Sorting a list is one of the first problems every programmer solves, and bubble sort is usually the first algorithm they solve it with. It is not fast, and it is rarely the right choice outside a classroom — but it is short, needs no extra memory, and its behavior is easy to see step by step, which makes it a good starting point before looking at faster algorithms like quicksort or merge sort.

The idea

Bubble sort repeatedly walks through the list, comparing each pair of neighboring elements. If a pair is out of order, it swaps them. One full pass moves the largest remaining value all the way to the end of the list — like a bubble rising to the top — because every swap that finds it carries it one position further right.

After the first pass, the largest element is guaranteed to be in its final position, so the next pass only needs to consider everything before it. Repeating this for n - 1 passes over a list of n elements is enough to fully sort it, since each pass fixes at least one more element in place.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
int i = 0;
int j = 0;
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int k = 0; k < N; k++) {
        values[k] = k + 1;
    }

    srand(1);
    for (int k = N - 1; k > 0; k--) {
        int r = rand() % (k + 1);
        int tmp = values[k];
        values[k] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one comparison every few frames instead of
    // one per frame, so individual steps stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (values[j] > values[j + 1]) {
            int tmp = values[j];
            values[j] = values[j + 1];
            values[j + 1] = tmp;
        }

        j++;
        if (j >= N - 1 - i) {
            j = 0;
            i++;
            if (i >= N - 1) {
                done = true;
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int k = 0; k < N; k++) {
        if (!done && (k == j || k == j + 1)) {
            PlotColor(220, 60, 60);   // pair being compared
        } else if (k >= N - i) {
            PlotColor(70, 170, 90);   // already in final position
        } else {
            PlotColor(30, 100, 200);  // untouched
        }

        int height = values[k] * (plot_height - 20) / N;
        int x0 = k * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

The two nested loops mirror the two ideas above: the outer index i counts how many elements are already fixed in place at the end of the list, and the inner index j walks through the unsorted part comparing neighbors. Instead of printing anything, frame() draws the array as bars — height is value, color shows what the algorithm is currently doing:

• blue — untouched, still unsorted
• red — the pair currently being compared
• green — already in its final position

To keep individual comparisons visible instead of finishing instantly, the sample only performs one comparison every few calls to frame() (see the tick counter) — everything else, including the array shuffle in setup(), runs exactly once.

Walking through an example

For the list [5, 1, 4, 2, 8], the first pass compares each neighboring pair left to right:

8 — the largest value — has bubbled into its final position after just one pass. The remaining passes repeat the same process over the shrinking unsorted prefix [1, 4, 2, 5], [1, 2, 4], and so on, until nothing is left to compare.

Why it is rarely used

Each pass is O(n) work, and a full sort needs up to n - 1 passes, so bubble sort is O(n²) in the worst and average case — quadratically worse than the O(n log n) of merge sort or quicksort. A common optimization tracks whether any swap happened during a pass and stops early if not, which brings the best case (an already-sorted list) down to O(n). The version here skips that check to keep the code and the visualization simple; every run does the full n - 1 passes regardless of the input.

Its value today is almost entirely pedagogical: it is the simplest possible introduction to comparison-based sorting, and a useful baseline to compare against faster algorithms that solve the same problem with cleverer strategies — dividing the list instead of scanning it repeatedly, in the case of merge sort and quicksort.

Conclusion

Bubble sort turns sorting into a sequence of local decisions: look at two neighbors, swap them if they are in the wrong order, and repeat until nothing is left to fix. That simplicity makes it a poor choice for large lists, but a good one for building intuition about what a sorting algorithm actually does — one comparison at a time.