Insertion sort (C)

From LiteratePrograms
Jump to: navigation, search
Other implementations: ACL2 | C | C, simple | Erlang | Forth | Haskell | Java | OCaml | Python, arrays | Standard ML | Visual Basic .NET

This is a simple example of the insertion sort sorting algorithm, written in C. Since this implementation is intended to be as simple and easy to under as possible, rather than particularly useful in practice, we will focus on sorting a simple array of ints of a given length.

[edit] Main algorithm

When sorting an array with insertion sort, we conceptually separate it into two parts:

  • The list of elements already inserted, which is always in sorted order and is found at the beginning of the array;
  • The list of elements we have yet to insert, following.

In outline, our primary function looks like this:

<<insertion_sort>>=
/* Sort an array of integers */
void insertion_sort(int a[], int length) {
    int i;
    for (i=0; i < length; i++) {
        insert a[i] into sorted sublist
    }
}

To insert each element, we need to create a hole in the array at the place where it belongs, then place it in it. We can combine the creation of the hole with the searching for the place by starting at the end and shifting each element up by one until we find the place where it belongs. This overwrites the element we're inserting, so we have to save it in a variable first:

<<insert a[i] into sorted sublist>>=
/* Insert a[i] into the sorted sublist */
int j, value = a[i];
for (j = i - 1; j >= 0; j--) {
    if (a[j] <= value) break;
    a[j + 1] = a[j];
}
a[j + 1] = value;

On average, we move about half the elements of the already-sorted sublist to insert each element. Consequently, the total number of assignments on average to sort n elements is:

\sum_{i=0}^{n-1} i/2 = \frac{n(n+1)}{4} = O(n^2)

In the worst case, the list is in reverse sorted order, so that each element must push up all other elements encountered so far. The total number of assignments in this case is twice the average case:

\sum_{i=0}^{n-1} i = \frac{n(n+1)}{2}

[edit] Test driver

To try out the sort, we can write a simple test driver file with the following structure:

<<insertion_sort.c>>=
header files

insertion_sort

test main

Our test main will create a small array, sort it, then print out the result. We use the traditional "sizeof division" trick to get the array length at compile time:

<<test main>>=
int main(void) {
    test main variable declarations
    int a[] = {5,1,9,3,2};
    insertion_sort(a, sizeof(a)/sizeof(*a));
    print out a
    return 0;
}

A better test main might ask for numbers from the user. We print out the array by just invoking printf on each element in turn:

<<test main variable declarations>>=
unsigned int i;
<<print out a>>=
/* Print out a */
for(i=0; i<sizeof(a)/sizeof(*a); i++) {
    printf("%d\n", a[i]);
}

We use unsigned because the sizeof division result is unsigned. We'll need to include stdio.h for printf:

<<header files>>=
#include <stdio.h>

This completes our simple exposition of iterative insertion sort in C. On UNIX, you can build and run this sample using the following script:

<<build_and_run.sh>>=
#!/bin/bash
gcc -Wall -O2 insertion_sort.c -o insertion_sort
./insertion_sort
Download code
hijacker
hijacker
hijacker
hijacker