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" with the number of members "size" case insensitively. This implements the insertion sort algorithm on pages 80 and 81 of volume 3 of the second edition of "The Art of Computer Programming" by Donald E. Knuth, published in 1998. In this implementation, R is the same thing as K, and R_i in Knuth's notation is array[i], and lower case letters are used throughout. */ static void insertion_sort (const char ** array, int size) { int j; /* Loop from the second entry to the final one, and put each into order, keeping the list from 0 to j in order at all times. */ for (j = 1; j < size; j++) { /* The position we are looking at, which goes from j - 1 to 0 as we examine the list to see what item has a lower score than k. */ int i; /* The key we are going to sort. */ const char * k; k = array[j]; /* Go from j-1 to 0 until we find an entry lower than "k". */ for (i = j - 1; i >= 0; i--) { if (strcasecmp (array[i], k) < 0) { break; } /* Move this entry up by one. */ array[i + 1] = array[i]; } /* Put the key which was at "j" into the ordered position found in the above loop, which is i+1 since we subtracted one from i at the end of the above loop. We cannot use array[j] since that was overwritten as the entries were moved up by one in the loop above. */ array[i + 1] = k; } } int main () { printf ("Initially, the array looks like this:\n\n"); print_array (daredevils, n_daredevils); insertion_sort (daredevils, n_daredevils); printf ("\nAfter it is sorted, the array becomes\n\n"); print_array (daredevils, n_daredevils); return 0; }

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.

**Acknowledgements:** Santosh Shaw from India pointed out that an
earlier version of this page did not use a correct insertion sort
algorithm since it did not run in O(n) time when the list was already
sorted.

Copyright © Ben Bullock 2009-2019. All
rights reserved.
For comments, questions, and corrections, please email
Ben Bullock
(*benkasminbullock@gmail.com*) or use the discussion group at Google Groups.
/
Privacy /
Disclaimer