// a structured quick sort algorithm written in pure C
// this is an adaptation of an adaptation of Tony Hoare's original algorithm
// credits to my teacher for the original structured adaptation
// I changed his function to make it work with arbitrary pointers, not just
// an array and 2 indexes.
// There is quite a bit of repeated code,
// but it's a decent price to pay for otherwise clean, structured code.
//
// begin has to be before end in memory.
void qsort( int *begin, int *end ) {
int *b = begin, *e = end, aux,
pivot = begin[ (begin - end) / 2 ]; // the pivot is the middle of the array
// search for the first element that's greater than or equal to the pivot
while ( *b < pivot )
b++;
// search for the first element that's less than or equal to the pivot
while ( *e > pivot )
e--;
while ( b < e ) { // if the pointers haven't crossed
aux = *b; // swap the values
*b = *e;
*e = aux;
// search for the first element that's greater than or equal to the pivot
do
b++;
while ( *b < pivot );
// search for the first element that's less than or equal to the pivot
do
e--;
while ( *e > pivot );
}
// now [ begin..e ] are less than or equal to the pivot...
if ( begin < e )
qsort( begin, e );
// ...and [ e + 1..end ] are greate than or equal to it
if ( e + 1 < end )
qsort( e + 1, end );
}