Unit 5 · Lesson 522 minAcademic review pending

Three ways to put an array in order

Bubble, insertion and selection sort all take about the same time on large arrays but differ in how they move data — and in how they behave on data that is nearly sorted.

Choose explanation

After this lesson

You should be able to

Implement bubble, insertion and selection sort.
Trace one pass of each on the same small array.
Say which one benefits when the data is nearly sorted.

Bubble sort: swap neighbours repeatedly

Compare each adjacent pair and swap them if they are out of order. After one full pass the largest value has travelled to the end. Repeat on the shrinking front portion until no swaps happen.

The swapped flag is what makes it useful: if a pass makes no swaps the array is already sorted and the function stops. On nearly sorted data that turns it into a single quick pass.

The flag turns a sorted array into one cheap pass

void bubble_sort(int a[], int n)
{
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;

        for (int i = 0; i < n - 1 - pass; i++)
            if (a[i] > a[i + 1]) {
                int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = 1;
            }

        if (!swapped) return;      /* already sorted */
    }
}

Insertion sort: place each card in a sorted hand

This is how people sort playing cards. Take the next element and slide it left past everything larger until it sits in the right place. Everything to its left is already in order.

It shines on nearly sorted data: each element moves only a step or two, so the work is close to linear. Of these three, it is the one worth reaching for in practice on small or almost-ordered arrays.

Shift larger elements right, then place the key

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];       /* shift right */
            j--;
        }
        a[j + 1] = key;            /* drop it in */
    }
}

Selection sort, and how they compare

Selection sort, from Unit III, finds the smallest remaining element and swaps it into place. Its distinguishing feature is that it makes at most n - 1 swaps — far fewer than bubble sort — which matters when moving an element is expensive, such as large structures.

All three compare roughly n squared times on large arrays, so none is suitable for very large data — that is what quicksort and mergesort are for, in a later course. The reason to learn these is that they are short enough to reason about completely.

The same array after one step of each

Array: 5 1 4 2

bubble    pass 1: 1 4 2 5   (largest reaches the end)
insertion step 1: 1 5 4 2   (1 slides left past 5)
selection pass 1: 1 5 4 2   (smallest swapped to front)

Try it yourself

Sort the same array with all three algorithms and count the swaps each performs.

Need a hint?

Insertion sort shifts rather than swaps, so count element moves for a fair comparison.

Check the worked solution

On this nearly-sorted input the counts differ sharply: bubble sort's flag lets it finish early, insertion sort shifts only a little, and selection sort still scans the full remaining range every pass regardless of how ordered the data already is. That last point is the one worth remembering — selection sort never gets faster on easy input.

#include <stdio.h>
#define SIZE 6

void show(const char *label, const int a[], int n, int moves)
{
    printf("%-10s ", label);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("  (%d moves)\n", moves);
}

int main(void)
{
    int base[SIZE] = {1, 2, 3, 5, 4, 6};   /* nearly sorted */
    int a[SIZE], moves;

    /* bubble */
    for (int i = 0; i < SIZE; i++) a[i] = base[i];
    moves = 0;
    for (int pass = 0; pass < SIZE - 1; pass++) {
        int swapped = 0;
        for (int i = 0; i < SIZE - 1 - pass; i++)
            if (a[i] > a[i + 1]) {
                int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                swapped = 1; moves++;
            }
        if (!swapped) break;
    }
    show("bubble", a, SIZE, moves);

    /* insertion */
    for (int i = 0; i < SIZE; i++) a[i] = base[i];
    moves = 0;
    for (int i = 1; i < SIZE; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; moves++; }
        a[j + 1] = key;
    }
    show("insertion", a, SIZE, moves);

    /* selection */
    for (int i = 0; i < SIZE; i++) a[i] = base[i];
    moves = 0;
    for (int i = 0; i < SIZE - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < SIZE; j++)
            if (a[j] < a[smallest]) smallest = j;
        if (smallest != i) {
            int t = a[i]; a[i] = a[smallest]; a[smallest] = t;
            moves++;
        }
    }
    show("selection", a, SIZE, moves);

    return 0;
}

Quick check

Which algorithm benefits most when the array is already nearly sorted?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Basic algorithms to sort array of elements (Bubble, Insertion and Selection sort algorithms)

Maps to course outcome CO6.