#include <stdio.h>
/* For "strcmp". */
#include <string.h>

/* This swaps two elements of "array" indexed by "a" and "b". */

static void swap (const char ** array, int a, int b)
{
    const char * holder;

    printf ("Swapping entry %d, '%s' to %d, and entry %d, '%s' to %d.\n",
            a, array[a], b, b, array[b], a);

    holder = array[a];
    array[a] = array[b];
    array[b] = holder;
}

/* This is an example implementation of the quick sort algorithm. */

static void quick_sort (const char ** array, int left, int right)
{
    int pivot;
    int i;
    int j;
    const char * key;

    /* Catch the trivial case. */

    if (right - left == 1) {
        if (strcmp (array[left], array[right]) > 0) {
	    printf ("Only one entry: ");
            swap (array, left, right);
        }
        return;
    }

    /* Pick a mid point for the pivot. */

    pivot = (left + right) / 2;
    key = array[pivot];
    printf ("Sorting from %d to %d: pivot (midpoint) is at %d, '%s'\n",
            left, right, pivot, key);

    /* Put the pivot key at the left of the list. */

    swap (array, left, pivot);

    i = left + 1;
    j = right;

    while (i < j) {
        while (i <= right && strcmp (array[i], key) < 0) {
            /* Leave the parts on the left of "key" in place if
               they are smaller than or equal to "key". */
            i++;
        }
        while (j >= left && strcmp (array[j], key) > 0) {
            /* Leave the parts on the right of "key" in place if
               they are greater than "key". */
            j--;
        }
        if (i < j) {
            /* "array[i]" is greater than "key", and "array[j]" is
               less than or equal to "key", so swap them. */
	    printf ("Out of order: '%s' > '%s', but %d < %d: ",
		    array[i], array[j], i, j);
            swap (array, i, j);
        }
    }
        
    /* Put the pivot key back between the two sorted halves. */

    printf ("Putting the pivot back: ");
    swap (array, left, j);

    if (left < j - 1) {
	printf ("Sub-sorting lower entries.\n");
        /* Sort the left half using this function recursively. */
        quick_sort (array, left, j - 1);
    }
    if (j + 1 < right) {
	printf ("Sub-sorting upper entries.\n");
        /* Sort the right half using this function recursively. */
        quick_sort (array, j + 1, right);
    }
}

/* This is the example data to sort. */

const char * monsters[] = {
    "jabberwocky",
    "werewolf",
    "dracula",
    "zebedee",
    "captain pugwash",
    "the clangers",
    "magilla gorilla",
    "hong kong phooey",
    "spartacus",
    "billy the silly billy",
};

/* "n_monsters" is the number of things to sort. */

#define n_monsters (sizeof monsters)/(sizeof (const char *))

/* This prints the contents of "array". */

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

int main ()
{
    printf ("Before sorting:\n\n");
    print_array (monsters, n_monsters);
    quick_sort (monsters, 0, n_monsters - 1);
    printf ("\nAfter sorting:\n\n");
    print_array (monsters, n_monsters);

    return 0;
}