Page 247 - Programming Microcontrollers in C

232 Chapter 5 Programming Large 8-Bit Systems

The outer loop in the preceding routine controls the way that the
array is split. It first splits the array in half and then shrinks the arrays
by halves until the sub arrays become zero in width. The second loop
steps along the elements of the arrays, and the third loop compares the
elements that are separated by split and swaps them when necessary.
The quick sort is:
/* quick_sort( int v[ ], int left, int right) :
sort the array v into ascending order */
void quick_sort(int v[ ], int left, int right)
{
int i,pivot;
if(right > left)
{
swap(v+left, v+(right+left)/2); /* chose the
value at center to pivot on */
pivot = left;
for(i=left+1; i<=right; i++)
if(v[i] < v[left])
swap(v+(++pivot), v+i);
swap(v+left, v+pivot); /* put the partition
element in place*/
quick_sort(v,left, pivot-1);
quick_sort(v,pivot+1,right);
}
}
The swap routine for both of these sorts is the same:

/* swap(int *, int *) : swap two integers in an
array */
void swap(int *i, int *j)
{
int temp;
temp = *i;
*i=*j;
*j=temp;
}

One of the nice things about both of these programs is that the swap
operation is not built into the program. Therefore, you can swap values