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.

Copyright © Ben Bullock 2009-2018. 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