jario_
Back to overview

Algorithms and Data Structures · Chapter 2

Simple sorting algorithms

Binary search from the last chapter needs a sorted array. But how does an array get sorted? In this chapter you get to know the three classic simple algorithms: bubble sort, selection sort and insertion sort. They are not the fastest, but they are easy to understand, and they come up in almost every exam.

Bubble sort

All three algorithms sort in place: they work directly in the array passed in and need no further memory apart from a few variables. Their basic building block is swapping two elements with a helper variable.

Bubble sort works in passes from left to right and always compares two neighbours. If the left element is larger, they are swapped. After the first pass the largest element is on the far right, after the second the second largest is in front of it, and so on. Pass i therefore only has to compare up to a.length - 1 - i.

Early exit: if a pass did not swap anything, the array is sorted and the loop ends with break.

import java.util.Arrays;
public class Main {    public static void bubbleSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            boolean swapped = false;            for (int j = 0; j < a.length - 1 - i; j++) {                if (a[j] > a[j + 1]) {                    int tmp = a[j];                    a[j] = a[j + 1];                    a[j + 1] = tmp;                    swapped = true;                }            }            System.out.println("Pass " + (i + 1) + ": " + Arrays.toString(a));            if (!swapped) {                break;            }        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        bubbleSort(a);    }}

Selection sort

Selection sort looks for the index of the smallest element in the unsorted rest and swaps it to the first free position. A sorted area grows on the left, one element per step.

There is at most one swap per step, so only n - 1 in total. In return, selection sort always compares the same amount, even if the array is already sorted: it only knows that an element is the smallest once it has looked at the whole rest.

import java.util.Arrays;
public class Main {    public static void selectionSort(int[] a) {        for (int i = 0; i < a.length - 1; i++) {            int min = i;            for (int j = i + 1; j < a.length; j++) {                if (a[j] < a[min]) {                    min = j;                }            }            int tmp = a[i];            a[i] = a[min];            a[min] = tmp;            System.out.println("Step " + (i + 1) + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        selectionSort(a);    }}

Insertion sort

Insertion sort works like sorting playing cards in your hand: on the left there is a sorted area. You keep the next element in key. All larger elements in the sorted area move one position to the right, and key goes into the gap.

Elements are shifted, not swapped. The condition j >= 0 && a[j] > key has to be in exactly this order: if j is already -1, && prevents a[-1] from being read.

If the array is almost sorted, hardly anything has to be shifted. Then insertion sort is very fast.

import java.util.Arrays;
public class Main {    public static void insertionSort(int[] a) {        for (int i = 1; i < a.length; i++) {            int key = a[i];            int j = i - 1;            while (j >= 0 && a[j] > key) {                a[j + 1] = a[j];                j--;            }            a[j + 1] = key;            System.out.println("Insert " + key + ": " + Arrays.toString(a));        }    }
    public static void main(String[] args) {        int[] a = {6, 2, 9, 1, 5};        insertionSort(a);    }}

Running time and stability

For an array with n elements, bubble sort makes (n - 1) + (n - 2) + … + 1 = n · (n - 1) / 2 comparisons in the worst case. That grows with n²: with twice as many elements it takes about four times as long. This is written O(n²).

  • Bubble sort (with early exit): best case O(n) if already sorted, worst case O(n²), stable.
  • Selection sort: always O(n²) comparisons, even in the best case, not stable.
  • Insertion sort: best case O(n) if already sorted, worst case O(n²) if sorted in reverse, stable.

Stable means: elements with the same key keep their order. This matters when you sort objects by one attribute, such as a ranking by points. Bubble sort and insertion sort only swap or shift when an element is strictly larger. Selection sort is not stable, because the swap can throw an element far to the back, past equal ones.

import java.util.Arrays;
public class Main {    record Card(String suit, int rank) {}
    // Stable: equal ranks keep their order.    public static void insertionSort(Card[] cards) {        for (int i = 1; i < cards.length; i++) {            Card key = cards[i];            int j = i - 1;            while (j >= 0 && cards[j].rank() > key.rank()) {                cards[j + 1] = cards[j];                j--;            }            cards[j + 1] = key;        }    }
    // Not stable: the swap can jump over equal ranks.    public static void selectionSort(Card[] cards) {        for (int i = 0; i < cards.length - 1; i++) {            int min = i;            for (int j = i + 1; j < cards.length; j++) {                if (cards[j].rank() < cards[min].rank()) {                    min = j;                }            }            Card tmp = cards[i];            cards[i] = cards[min];            cards[min] = tmp;        }    }
    public static void main(String[] args) {        Card[] cards = {            new Card("hearts", 5), new Card("spades", 5), new Card("clubs", 2)        };        Card[] a = cards.clone();        insertionSort(a);        System.out.println("Insertion: " + Arrays.toString(a));        Card[] b = cards.clone();        selectionSort(b);        System.out.println("Selection: " + Arrays.toString(b));    }}

Two cards with rank 5: insertion sort keeps hearts before spades, selection sort swaps them.

Common mistakes

  • Inner loop one step too far

    If you compare a[j] with a[j + 1], j may only run while j < a.length - 1 - i. With j < a.length - i, the first pass accesses a[a.length] and you get an ArrayIndexOutOfBoundsException. The other way round, with a bound that is too small, the last pair is never compared and the result is sorted wrongly, without any error message.

  • Remembering the value instead of the index

    In selection sort, min has to be the index of the smallest element, not its value. With only the value, you don't know at the end which position to swap with:

    int min = a[i];   // wrong: valueint min = i;      // right: index, compare a[j] < a[min]

  • Losing stability with >=

    If insertion sort shifts with a[j] >= key instead of a[j] > key, the array is still sorted, but equal elements overtake each other. With numbers you don't notice, with a ranking with equal points you do. The same goes for bubble sort: only swap on >.