Example of insertion sort in C

This is an example C program demonstrating "insertion sort".

#include <stdio.h>
#include <string.h>

const char * daredevils[] = {
    "Evel Knievel",
    "Freaky Franky the Visible Man",
    "Penelope Pitstop",
    "Batman AKA Clark Kent, the loudmouthed detective",
    "Ringo Starr AKA Richard Starkey",
    "Brad Pitt",
    "Keano Reeves",
    "Gary Seven",
    "Awful Knoffel",
};

#define n_daredevils (sizeof (daredevils) / sizeof (const char *))

static void print_array (const char ** array, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        printf ("%d: %s\n", i, array[i]);
    }
}

/* Sort the contents of "array" case insensitively. */

static void insertion_sort (const char ** array, int size)
{
    int i;
    for (i = 0; i < size; i++) {
        int j;
        for (j = i; j < size; j++) {
            if (strcasecmp (array[i], array[j]) > 0) {
                /* Swap the contents of array[i] and array[j]. */
                const char * t;
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
    }
}

int main ()
{
    printf ("Initially, the array looks like this:\n\n");
    print_array (daredevils, n_daredevils);
    printf ("\nAfter it is sorted, the array becomes\n\n");
    insertion_sort (daredevils, n_daredevils);
    print_array (daredevils, n_daredevils);
    return 0;
}

(download)

The output of the example looks like this:

Initially, the array looks like this:

0: Evel Knievel
1: Freaky Franky the Visible Man
2: Penelope Pitstop
3: Batman AKA Clark Kent, the loudmouthed detective
4: Ringo Starr AKA Richard Starkey
5: Brad Pitt
6: Keano Reeves
7: Gary Seven
8: Awful Knoffel

After it is sorted, the array becomes

0: Awful Knoffel
1: Batman AKA Clark Kent, the loudmouthed detective
2: Brad Pitt
3: Evel Knievel
4: Freaky Franky the Visible Man
5: Gary Seven
6: Keano Reeves
7: Penelope Pitstop
8: Ringo Starr AKA Richard Starkey

See also this Example of quicksort in C. Quicksort is another algorithm for sorting. It is more complex than insertion sort, but for long lists it is quicker.


Copyright © Ben Bullock 2009-2017. All rights reserved. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com). / Privacy / Disclaimer