Bubble, selection and insertion sort

Introduction

Sorting puts items in order. These three sorts are simple, sort in place (no second array), and take O(n²) time in the worst case. They are fine for small arrays, and they are the base for understanding the faster sorts that follow.

These sorts are not what you would use for a million items, but they teach what a sort actually does. Knowing them also explains why fast library sorts still hand small pieces to insertion sort.

How it works

Bubble sort

#include <stdio.h>

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

void bubble_sort(int a[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; 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;   // no swaps: already sorted
    }
}

int main(void) {
    int a[] = {5, 1, 4, 2, 8};
    bubble_sort(a, 5);
    print(a, 5);
    return 0;
}

Compare each pair of neighbours and swap them if they are in the wrong order. After the first pass the largest item has "bubbled" to the end; after the second, the second largest; and so on. If a whole pass makes no swap, the array is sorted and the loop stops early, so an already sorted array takes only one pass: O(n).

Selection sort

#include <stdio.h>

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

void selection_sort(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;
    }
}

int main(void) {
    int a[] = {29, 10, 14, 37, 13};
    selection_sort(a, 5);
    print(a, 5);
    return 0;
}

Find the smallest item and swap it into position 0; then the smallest of the rest into position 1; and so on. It always does n(n-1)/2 comparisons, even on sorted input, but at most n - 1 swaps, which helps when writing to memory is expensive.

Syntax

int key = a[i];                // lift the item out
while (j >= 0 && a[j] > key) { // shift larger items right
    a[j + 1] = a[j];
    j--;
}
a[j + 1] = key;                // drop it into the gap

Example

#include <stdio.h>

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

void insertion_sort(int a[], int n) {
    for (int i = 1; i < n; 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;
    }
}

int main(void) {
    int a[] = {12, 11, 13, 5, 6};
    insertion_sort(a, 5);
    print(a, 5);
    return 0;
}

Keep the left part a[0 .. i-1] sorted. Take the next item key = a[i], move larger items of the sorted part one place right, and drop key into the gap, like sorting playing cards in your hand. On nearly sorted data it does almost no work, which is why fast library sorts switch to insertion sort for small pieces.

A sort is stable if equal items keep their original order. That matters when sorting records: sort students by name, then stably by mark, and students with equal marks stay in name order.

Line by line

1. print writes the array on one line, so it can be reused after sorting.
2. In insertion_sort, i starts at 1, because one item on its own is already sorted.
3. key saves a[i], since shifting would otherwise overwrite it.
4. The while loop moves every larger item one place right. Testing j >= 0 first means a[-1] is never read.
5. When the loop stops, a[j] is not larger than key, so a[j + 1] is the gap where key belongs.
6. main sorts five numbers and prints them in increasing order.

Expected result

5 6 11 12 13 

In the real world

Timsort, the sort built into Python and used for objects in Java, finds runs that are already in order and uses insertion sort on short pieces. Stable sorting is why a spreadsheet can be sorted by name and then by city, and still show the names in order within each city.

Common mistakes

• Letting the inner loop of bubble sort read a[j + 1] one place past the end of the array.
• Writing a[j] >= key in insertion sort, which moves equal items and makes the sort unstable.
• Forgetting to save the key before shifting, so its value is lost.

Best practices

• Trace a sort by hand on five items before coding it.
• Use insertion sort for small or nearly sorted arrays.
• Use your library's sort for real data.

Summary

Bubble, selection and insertion sort each build a sorted part step by step in O(n²) worst-case time. They differ in how many moves they make, in how they behave on nearly sorted data, and in whether they are stable.

Mark lesson complete