Bytebook Compiler

Searching & Sorting

Bubble, Selection & Insertion Sort

The three O(n²) sorts: how each one works, passes and swaps traced by hand, stability, best cases, and when a simple sort is the right choice.

4 min read3 runnable examplesInteractive4-question quiz

Sorting puts elements in order. Sorted data makes searching (binary search), finding duplicates, merging and reporting much easier. We start with three simple sorts that are easy to trace by hand — exactly what exams ask.

Watch them run on the same data:

Bubble sort

Compare adjacent pairs and swap if they are in the wrong order. After pass 1 the largest element has "bubbled" to the end; after pass 2, the second largest; and so on. If a pass makes no swaps, the array is already sorted and we can stop early.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void bubbleSort(int a[], int n) {
    for (int pass = 1; pass < n; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - pass; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = 1;
            }
        printf("after pass %d: ", pass); show(a, n);
        if (!swapped) break;                 // no swaps: already sorted
    }
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    bubbleSort(a, 5);
    return 0;
}
Output
after pass 1: 1 4 2 5 8 
after pass 2: 1 2 4 5 8 
after pass 3: 1 2 4 5 8
Try it Yourself

Selection sort

Find the minimum of the unsorted part and swap it to the front of that part. Exactly n − 1 swaps — useful when writing to memory is expensive.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
        printf("pass %d (placed %d): ", i + 1, a[i]); show(a, n);
    }
}

int main(void) {
    int a[] = {64, 25, 12, 22, 11};
    selectionSort(a, 5);
    return 0;
}
Output
pass 1 (placed 11): 11 25 12 22 64 
pass 2 (placed 12): 11 12 25 22 64 
pass 3 (placed 22): 11 12 22 25 64 
pass 4 (placed 25): 11 12 22 25 64
Try it Yourself

Insertion sort

Build the sorted part one element at a time: take the next element (the key) and shift larger sorted elements right until the key's place is found — the way you sort playing cards in your hand.

C
#include <stdio.h>

void show(const int a[], int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); printf("\n"); }

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];                 // shift right
            j--;
        }
        a[j + 1] = key;
        printf("insert %2d: ", key); show(a, n);
    }
}

int main(void) {
    int a[] = {12, 11, 13, 5, 6};
    insertionSort(a, 5);
    return 0;
}
Output
insert 11: 11 12 13 5 6 
insert 13: 11 12 13 5 6 
insert  5: 5 11 12 13 6 
insert  6: 5 6 11 12 13
Try it Yourself

On nearly sorted data, insertion sort barely shifts anything and runs in close to O(n) — which is why fast library sorts switch to insertion sort for small pieces.

Comparison

Bubble Selection Insertion
Best case O(n) (with early exit) O(n²) O(n)
Average / worst O(n²) O(n²) O(n²)
Swaps / writes many n − 1 swaps many shifts
Extra space O(1) O(1) O(1)
Stable? yes no yes
Adaptive (faster on sorted input)? yes no yes

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    After the first pass of bubble sort on [4, 3, 2, 1], what is the array?

  2. 2

    Which simple sort makes at most n − 1 swaps?

  3. 3

    Which sort is fastest on an already sorted array?

  4. 4

    Which of these is not stable?

Esc
↑↓ move↵ open