Bubble, selection and insertion sort

Why it exists

The first sorting algorithms anyone writes are short, in place and easy to get right, and they run in time proportional to $n^2$. They are not used for large inputs, but they matter for three reasons: GATE asks about their exact counts (comparisons, swaps) on particular inputs; one of them, insertion sort, is the fastest simple method for small or nearly sorted inputs and is the finishing step inside the fast sorts; and the idea of inversions that explains them also explains why no algorithm that moves one neighbour at a time can be fast.

Prerequisites

You need to count loop iterations and nested loops (analysing loops).

Precise definitions

Sorting. Rearrange $a_0, \ldots, a_{n-1}$ so that $a_0 \le a_1 \le \cdots \le a_{n-1}$. The output must be a permutation of the input.

Comparison sort. An algorithm that learns about the order of the keys only by comparing two of them. All sorts on this page are comparison sorts.

In place. Uses only $O(1)$ extra memory besides the array.

Stable. Keys that are equal appear in the output in the same order as in the input (stability and comparison of sorts).

Inversion. A pair of positions $i < j$ with $a_i > a_j$. A sorted array has $0$ inversions, a strictly decreasing array has $n(n-1)/2$. The number of inversions measures how far an array is from sorted. Averaged over all $n!$ orderings of distinct keys it is $n(n-1)/4$.

Adaptive. Runs faster on inputs that are already nearly sorted.

How it works

Bubble sort. Repeatedly walk through the array comparing neighbours and swapping those that are out of order. After pass $p$ the largest $p$ keys are in their final places at the right end, so each pass can stop one position earlier. If a pass makes no swap the array is sorted and the algorithm can stop (the early exit).

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;
    }
}

Selection sort. Find the smallest key of the unsorted part and swap it into the first unsorted position. After pass $i$ the $i + 1$ smallest keys are in their final places.

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;
        if (min != i) { int t = a[i]; a[i] = a[min]; a[min] = t; }
    }
}

Insertion sort. Keep a sorted prefix. Take the next key, shift the larger keys of the prefix one place to the right, and drop the key into the gap. The prefix grows by one; the keys of the prefix are not yet in their final places (a later small key will move them).

void insertion_sort(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];
            j--;
        }
        a[j + 1] = key;
    }
}

Measured counts. The C program below runs all three on five inputs of $8$ keys and counts comparisons of keys and moves (swaps for bubble and selection sort, shifts for insertion sort). Its code is the same as above with counters added, and it was compiled and run to produce the output.

#include <stdio.h>
 
typedef struct { int cmp, mv; } Count;   /* comparisons of keys; swaps (bubble, selection) or shifts (insertion) */
 
static Count bubble(int a[], int n) {
    Count c = {0, 0};
    for (int pass = 0; pass < n - 1; pass++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; j++) {
            c.cmp++;
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                c.mv++;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
    return c;
}
 
static Count selection(int a[], int n) {
    Count c = {0, 0};
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            c.cmp++;
            if (a[j] < a[min]) min = j;
        }
        if (min != i) {
            int t = a[i]; a[i] = a[min]; a[min] = t;
            c.mv++;
        }
    }
    return c;
}
 
static Count insertion(int a[], int n) {
    Count c = {0, 0};
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && (c.cmp++, a[j] > key)) {   /* the comma counts every comparison of keys */
            a[j + 1] = a[j];
            c.mv++;
            j--;
        }
        a[j + 1] = key;
    }
    return c;
}
 
static int inversions(const int a[], int n) {
    int inv = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[i] > a[j]) inv++;
    return inv;
}
 
int main(void) {
    const char *name[5] = {"sorted", "reversed", "one swap", "mixed", "all equal"};
    int in[5][8] = {{1, 2, 3, 4, 5, 6, 7, 8}, {8, 7, 6, 5, 4, 3, 2, 1}, {1, 2, 4, 3, 5, 6, 7, 8}, {5, 1, 4, 2, 8, 7, 3, 6}, {4, 4, 4, 4, 4, 4, 4, 4}};
    printf("%-10s %3s | %-9s | %-9s | %-9s\n", "input", "inv", "bubble", "selection", "insertion");
    for (int r = 0; r < 5; r++) {
        int x[8], y[8], z[8];
        for (int i = 0; i < 8; i++) x[i] = y[i] = z[i] = in[r][i];
        int inv = inversions(in[r], 8);
        Count b = bubble(x, 8), s = selection(y, 8), t = insertion(z, 8);
        printf("%-10s %3d | %3d %3d   | %3d %3d   | %3d %3d\n", name[r], inv, b.cmp, b.mv, s.cmp, s.mv, t.cmp, t.mv);
    }
    return 0;
}

input      inv | bubble    | selection | insertion
sorted       0 |   7   0   |  28   0   |   7   0
reversed    28 |  28  28   |  28   4   |  28  28
one swap     1 |  13   1   |  28   1   |   8   1
mixed       11 |  25  11   |  28   7   |  17  11
all equal    0 |   7   0   |  28   0   |   7   0

What the numbers say, and why.

• Inversions are the common currency. Bubble sort swaps adjacent keys that are in the wrong order, and every such swap removes exactly one inversion, so it makes exactly $I$ swaps, where $I$ is the number of inversions. Insertion sort shifts a key past exactly the larger keys before it, which are exactly the inversions that key forms, so it makes exactly $I$ shifts. In the table the swaps of bubble sort and the shifts of insertion sort equal the inversion column in every row.
• Selection sort ignores the input. Finding the minimum of $n - i$ keys takes $n - i - 1$ comparisons however they are ordered, so the total is always $n(n-1)/2$ ($28$ for $n = 8$ in every row). It makes at most $n - 1$ swaps, the fewest of the three, which matters when moving a record is expensive.
• Bubble sort with the early exit makes $n - 1$ comparisons on a sorted array (one pass) and $n(n-1)/2$ on a reversed one. The number of passes is $1 +$ the largest number of larger keys to the left of any key (at most $n - 1$), because each pass moves a key left by at most one place.
• Insertion sort makes one failed comparison per key unless the key goes to the very front, so its comparisons are $I + (n - 1) - f$, where $f$ is the number of keys that are smaller than everything before them: between $n - 1$ (sorted) and $n(n-1)/2$ (reversed). It is adaptive: its time is $\Theta(n + I)$.
• Worst case for all three is $\Theta(n^2)$; best case is $\Theta(n)$ for bubble sort with the early exit and for insertion sort, and $\Theta(n^2)$ for selection sort. Average case over random permutations of distinct keys: $I = n(n-1)/4$ swaps or shifts, so $\Theta(n^2)$ for all three.

Binary insertion sort. The place for the key inside the sorted prefix can be found with binary search (binary search), cutting the comparisons to $\sum \lceil \log_2 (i + 1) \rceil = O(n \log n)$. But the shifts remain $I$, so the time is still $\Theta(n^2)$ in the worst case.

Why adjacent swaps cannot be fast. One swap of two adjacent keys changes the number of inversions by at most one (by exactly one when the two keys differ). An array with $I$ inversions therefore needs at least $I$ such swaps. Since a random array has $n(n-1)/4$ inversions on average, any sort that moves keys only by adjacent swaps takes $\Omega(n^2)$ time on average. The faster sorts (merge, quick, heap) win by moving a key over a long distance in one step, which removes many inversions at once.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The properties asked about on these sorts (stable, in place, adaptive) are compared with the fast sorts in stability and comparison of sorts. The fast sorts are merge sort, quicksort and heap sort; the reason $n \log n$ is the best possible for comparison sorts is in lower bound and linear-time sorts. The comparison counts here use the loop analysis of analysing loops.

PYQs

The worst-case running time of Insertion sort,
Merge sort and Quick sort, respectively, are:

Which one of the following is the tightest upper
bound that represents the number of swaps
required to sort n numbers using selection sort?

The pseudocode of a function fun() is given below:

fun(int A[0,...,n-1])
{
    for i=0 to n-2
    for j-0 to n-i-2
        if (A[j] > A[j+1])
        then swap A[j] and A[j+1]}
}

The pseudocode of a function fun() is given below:
fun(int A[0,...,n-1])
{
    for i=0 to n-2
    for j-0 to n-i-2
        if (A[j] > A[j+1])
        then swap A[j] and A[j+1]}
}
Let A[0, ... ,29] be an array storing 30 distinct integers
in descending order. The number of swap operations
that will be performed, if the function fun0 is called
with A[0, ... ,29] as argument, is ____ . (Answer in
integer)

Consider the following snippet of a C program.
Assume that swap(&x, &y)  exchanges the contents
of x and y.
int main ()  {
    int array[] = {3, 5, 1, 4, 6, 2};
    int done = 0;
    int i;
while (done = = 0)  {
     done = 1;
     for (i=0; i<=4; i++)  {
            if (array[i] < array[i+1])  {
               swap (&array[i], &array[i+1]);
               done = 0;
        }
}
for (i=5;  i>=1;  i- -) {
      if (array[i] > array[i-1])   {
      swap(&array[i], &array[i-1]);
      done=0;
       }
     }
}
printf("%d", array[3]);
}
The output of the program is ________.

What is the worst case time complexity of inserting n
elements into an empty linked list, if the linked list
needs to be maintained in sorted order?

Self-check

Revision card

References