#include <stdio.h>
static void
qs (int *i, int *j)
{
int *first = i;
int *last = j;
int tmp;
/*
* Pick the middle element as pivot.
*
*/
const int pivot = *(i + ((j-i)/2));
while (i <= j)
{
/*
* | first pivot last |
* | | | | |
* | v v v |
* | 3 : 6 : 12 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 2 : 1 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*
* Increment i for as long as its pointee is strictly less than the pivot value.
*
*/
while (*i < pivot && i < last)
++i;
/*
* Decrement j for as long as its pointee is strictly greater than the pivot.
*
*/
while (*j > pivot && j > first)
--j;
/*
* | first pivot last |
* | | | | |
* | v v v |
* | 3 : 6 : 12 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 2 : 1 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*/
if (i > j)
break;
/*
* Swap the elements at position i and j.
*/
tmp = *i;
*i = *j;
*j = tmp;
/*
* | first pivot last |
* | | | | |
* | v v v |
* | 3 : 1 : 12 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 2 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*/
/*
* Move pointers forward in their respective order.
*/
i++;
j--;
/*
* | first pivot last |
* | | | | |
* | v v v |
* | 3 : 1 : 12 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 2 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*
*
* Then, in the next iteration of the while loop, this is what will happen.
*
*
* while (*i < pivot && i < last)
* ++i;
* while (*j > pivot && j > first)
* --j;
*
*
* Pointers will remain in their current positions.
*
*
* | first pivot last |
* | | | | |
* | v v v |
* | 3 : 1 : 12 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 2 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*
*
* ...swap
*
*
* | first last |
* | | | |
* | v v |
* | 3 : 1 : 2 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 12 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*
*
* ...and then, in the next iteration
*
*
* | first last |
* | | | |
* | v v |
* | 3 : 1 : 2 : 10 : 5 : 11 : 14 : 4 : 13 : 9 : 12 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | i j |
*
*
* And, finally, we end up with this (after a few more iterations):
*
*
* | first last |
* | | | |
* | v v |
* | 3 : 1 : 2 : 4 : 5 : 11 : 14 : 10 : 13 : 9 : 12 : 6 : 7 : 16 : 8 : 15 |
* | ^ ^ |
* | j i |
*
*/
}
/*
* Now we run the algorithm recursively on the two sub-lists.
*
*/
if (i < last)
{
/*
* 3 : 1 : 2 : 4 : 5 : 11 : 14 : 10 : 13 : 9 : 12 : 6 : 7 : 16 : 8 : 15
* ^ ^
* | |
* ----------------------------------------------------
* i
*/
qs (i, last);
}
if (j > first)
{
/*
* 3 : 1 : 2 : 4 : 5 : 11 : 14 : 10 : 13 : 9 : 12 : 6 : 7 : 16 : 8 : 15
* ^ ^
* | |
* -------------
* j
*/
qs (first, j);
}
}
static void
quicksort (int *n, size_t len)
{
qs (n, n + len - 1);
}
int
main (void)
{
int i;
int numbers[] = {3, 6, 12, 10, 5, 11, 14, 100, 4, 13, 9, 16, 2, 1, 7, 17, 8, 15};
size_t len = sizeof (numbers) / sizeof (int);
quicksort (numbers, len);
/* Print out the result */
for (i = 0; i < len; ++i)
printf ("%d ", numbers[i]);
printf ("\n");
return 0;
}