Simple sorting: bubble, selection, insertion

← back to the section

Data has to be sorted all the time: names alphabetically, products by price, events by time. Sorting is also the mandatory step before a fast binary search: it only works on ordered data. Let's start with the three simplest algorithms — not the fastest ones, but they show how sorting is built at all. The fast methods come later.

The two operations everything is built from

A person lines people up by height "by eye": they see everyone at once. A program cannot do that — it compares only two elements at a time. So any sort is made of two repeating actions:

1. compare two elements;
2. swap them (or copy one of them).

The three algorithms below differ only in how they pick which element to compare with which.

Bubble sort

The simplest (and slowest) method. We go left to right comparing adjacent pairs: if the left one is bigger, we swap them. By the end of the pass the largest element sits at the right edge — it has bubbled up. The next pass runs only to the second-to-last position, and so on.

In code that is two nested loops: the outer one moves the border of the sorted tail leftwards, the inner one walks pairs up to that border. Each pass puts exactly one element in place. Clear, but slow: about N² comparisons and a lot of swaps.

Selection sort

Here we cut down the number of swaps. The idea: in one pass we find the minimum among the elements that are not sorted yet and put it into the first free slot on the left. Then the minimum of what is left goes into the second slot, and so on.

There are just as many comparisons as in bubble sort — about N². But there is only one swap per pass: found the minimum, moved it once, instead of shuffling pairs back and forth. That is on the order of N swaps instead of N²; if the elements are heavy, this is a noticeable win.

Insertion sort

Usually the best of the three simple methods. This is how cards are arranged in a hand: on the left we keep the already ordered part, take the next element on the right and put it into its place, shifting the bigger ones right to free a gap.

On average there are about half as many comparisons as in bubble sort (roughly N²/4): an insertion stops as soon as the place is found instead of walking the whole length. There is no swapping here at all — elements are not exchanged in pairs, they are shifted right to free the gap; that is why the table below lists shifts for insertion. And insertion sort has one special trump card: on nearly ordered data it runs in almost linear time, O(N) — if an element is already in the right place, the insertion moves nothing. That is why it is used inside more complex algorithms — for small chunks in quicksort, for instance.

All three are O(N²)

Despite the differences, all three methods have the same growth rate — O(N²) (quadratic time): double the data and the work goes up fourfold. That is tolerable for tens and hundreds of elements, but for a million O(N²) means a trillion operations, which is already unacceptable. The difference between the three is in the constants and the number of swaps, not in the growth rate. Counters make it visible: let's sort the same array three ways and count comparisons and moves.

live example

import java.util.Arrays;

public class SortCost {
    static int comparisons, moves;

    static boolean greater(int x, int y) {
        comparisons++;
        return x > y;
    }

    static void swap(int[] a, int i, int j) {
        moves++;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }

    static void bubble(int[] a) {
        for (int out = a.length - 1; out > 0; out--)
            for (int in = 0; in < out; in++)
                if (greater(a[in], a[in + 1])) swap(a, in, in + 1);
    }

    static void selection(int[] a) {
        for (int out = 0; out < a.length - 1; out++) {
            int min = out;
            for (int in = out + 1; in < a.length; in++)
                if (greater(a[min], a[in])) min = in;
            swap(a, out, min);
        }
    }

    static void insertion(int[] a) {
        for (int out = 1; out < a.length; out++) {
            int temp = a[out], in = out;
            while (in > 0 && greater(a[in - 1], temp)) {
                a[in] = a[in - 1];
                in--;
                moves++;
            }
            a[in] = temp;
        }
    }

    static void print(String name, int[] a) {
        System.out.println(name + ": comparisons " + comparisons + ", moves " + moves
            + " -> " + Arrays.toString(a));
        comparisons = moves = 0;
    }

    public static void main(String[] args) {
        int[] data = {7, 3, 9, 1, 8, 2, 6, 4};
        int[] a = data.clone(); bubble(a); print("bubble", a);
        a = data.clone(); selection(a); print("selection", a);
        a = data.clone(); insertion(a); print("insertion", a);
    }
}

Bubble and selection both do 28 comparisons — every pair of the eight elements; insertion gets away with 21. Selection makes only 7 moves, one per pass; bubble and insertion make 16 each. For large N the ratios stay the same:

Of the simple methods the default choice is insertion sort; for large arrays none of the three will do — that needs the O(N·log N) league.

Stability

One more property that matters in practice is stability. A sort is stable when elements with equal keys keep their original relative order. This is what you need when sorting by several fields in turn: first by first name, then by last name — so that namesakes stay ordered by first name. Bubble and insertion sort are stable; selection sort in its naive form is not — a long-distance swap can jump over an equal element.

How this is done in Java

You almost never need to write bubble or insertion sort by hand: the standard library already has a sort and it is well tested. But what is inside decides whether the order of equal elements survives and how fast things run on nearly ordered data.

There are two entry points: Arrays.sort for arrays and Collections.sort (the same thing as list.sort(...)) for lists.

List<Employee> staff = new ArrayList<>(hired);
staff.sort(Comparator.comparing(Employee::lastName));

When objects are sorted, TimSort does the work — a hybrid of merge sort and insertion sort. First it scans the data for chunks that are already ordered (they are called runs); a short run is grown to a decent length with insertion sort, only a binary one — the place for the next element is found by binary search rather than by scanning from the left. Then the ready runs are merged. Hence two properties: TimSort is stable, and on nearly ordered data it runs close to O(N). In the worst case it is O(N·log N).

Insertion sort also stayed in the library in a supporting role: short stretches of a few dozen elements are finished off with it — at that length it beats everything else thanks to its tiny overhead.

One important difference: stability exists only in the object version. Arrays.sort(int[]) knows nothing about it and cannot — two equal numbers are indistinguishable, so "keeping their order" is meaningless.

The trap. TimSort trusts that comparison is consistent: if a is less than b and b is less than c, then a is less than c. The classic way to break that is comparing by subtraction:

Comparator<Item> byPrice = (a, b) -> (int) (a.priceInCents() - b.priceInCents());

The difference of two large numbers does not fit into an int, the sign comes out arbitrary and the order becomes contradictory. On short lists "everything works", and on a long one TimSort spots the inconsistency and kills the sort with IllegalArgumentException: Comparison method violates its general contract!. The safe form is Comparator.comparingLong(Item::priceInCents): it compares instead of subtracting.

In short

• Any sort is a repeated comparison and swap of two elements.
• Bubble sort walks adjacent pairs and the largest element floats to the end; simple, but slow.
• Selection sort finds the minimum and puts it at the front; the same number of comparisons, but few swaps.
• Insertion sort keeps an ordered part on the left and inserts the next element into it; usually the best of the three, especially on nearly sorted data (close to O(N) there).
• All three are O(N²): fine for small volumes, not for large ones. Stability keeps the order of equal elements — it matters when sorting by several fields.

What to read next

• Advanced sorting: Shell sort, quicksort, radix sort — how algorithms get from O(N²) to O(N·log N).
• Stacks and queues — structures with deliberately restricted access.
• Arrays, binary search and big O — why data is sorted before searching in the first place.
• Two pointers and the sliding window — techniques that only work on ordered data.