Example of quicksort in C

This is an example C program demonstrating the quicksort algorithm.

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

(download)

The output of the example looks like this:

Before sorting:

0: jabberwocky
1: werewolf
2: dracula
3: zebedee
4: captain pugwash
5: the clangers
6: magilla gorilla
7: hong kong phooey
8: spartacus
9: billy the silly billy

Sorting from 0 to 9: pivot (midpoint) is at 4, 'captain pugwash'
Swapping entry 0, 'jabberwocky' to 4, and entry 4, 'captain pugwash' to 0.
Out of order: 'werewolf' > 'billy the silly billy', but 1 < 9: Swapping entry 1, 'werewolf' to 9, and entry 9, 'billy the silly billy' to 1.
Putting the pivot back: Swapping entry 0, 'captain pugwash' to 1, and entry 1, 'billy the silly billy' to 0.
Sub-sorting upper entries.
Sorting from 2 to 9: pivot (midpoint) is at 5, 'the clangers'
Swapping entry 2, 'dracula' to 5, and entry 5, 'the clangers' to 2.
Out of order: 'zebedee' > 'spartacus', but 3 < 8: Swapping entry 3, 'zebedee' to 8, and entry 8, 'spartacus' to 3.
Putting the pivot back: Swapping entry 2, 'the clangers' to 7, and entry 7, 'hong kong phooey' to 2.
Sub-sorting lower entries.
Sorting from 2 to 6: pivot (midpoint) is at 4, 'jabberwocky'
Swapping entry 2, 'hong kong phooey' to 4, and entry 4, 'jabberwocky' to 2.
Out of order: 'spartacus' > 'dracula', but 3 < 5: Swapping entry 3, 'spartacus' to 5, and entry 5, 'dracula' to 3.
Putting the pivot back: Swapping entry 2, 'jabberwocky' to 4, and entry 4, 'hong kong phooey' to 2.
Sub-sorting lower entries.
Only one entry: Swapping entry 2, 'hong kong phooey' to 3, and entry 3, 'dracula' to 2.
Sub-sorting upper entries.
Only one entry: Swapping entry 5, 'spartacus' to 6, and entry 6, 'magilla gorilla' to 5.
Sub-sorting upper entries.
Only one entry: Swapping entry 8, 'zebedee' to 9, and entry 9, 'werewolf' to 8.

After sorting:

0: billy the silly billy
1: captain pugwash
2: dracula
3: hong kong phooey
4: jabberwocky
5: magilla gorilla
6: spartacus
7: the clangers
8: werewolf
9: zebedee

If you are very interested in performance, you may be interested in An example of an inline qsort, which compares the performance of qsort, an inline sorting routine in C, and the C++ standard template library's template-based sorting.