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