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

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.