Quicksort Files: sort.c, sort.h Quicksort is an exchange sort, and sorts an array, a[], by repeatedly exchanging array elements until they are sorted. Quicksort is described below using pseudo-code: quicksort(p, q) { if p < q { x = a[p]; partition(p, q, m); /* Note that m is a reference type parameter. */ quicksort(p, m-1); quicksort(m+1, q); } } partition(p, q, m) { /* m is a reference type parameter, so if m changes, the corresponding * variable argument in the function call changes. */ i = p; j = q + 1; x = a[p]; while i < j { repeat { j = j - 1; if(i == j) goto end_partition; } until a[j] < x; a[i] = a[j]; repeat { i = i + 1; if(i == j) goto end_partition; } until a[i] > x; a[j] = a[i]; } end_partition: a[i] = x; m = i; } main program { quicksort(1, n); } partition(p, q, m) selects a pivot array element, x, which in this case is the leftmost array element. All elements not greater than x are put in a[p .. m-1], and those not smaller than x in a[m-1 .. q], and x in a[m]. Quicksort proceeds to sort the array recursively by partitioning array elements, then calling quicksort on the two array regions a[p .. m-1] and a[m+1 .. q]. When the recursion proceeds deep enough for quicksort() to be called on an array region with length zero or length one, the array region is already sorted, and recursion ends. In the file sort.c quicksort has been implemented using two functions. Programs can call the function quicksort(), which requires the following argument: - A pointer to the array. - The number of array elements. - The size (in bytes) of an array element. - A pointer to a function that compares array elements. This has been implemented to have the same parameters as the qsort() function provided by the C header stdlib.h. The actual quicksort algorithm is implemented using the function quicksort_recursive(). The partitioning code is contained within quicksort_recursive(), rather than in a separate function. The quicksort_recursive() function has pointer parameters p and q which specify the array region being sorted. These are slightly different from the index parameters in the above algorithm. The void * parameters are pointers to bytes in the array. A pointer is made to point to the next array element by incrementing it by the size (in bytes) of array element. The global variables element_size and compare_fn are set up by quicksort() before quicksort_recursive() is called. quicksort_recursive() then knows the size of array elements, and has access to the comparison function. Pivot selection during partitioning can be improved by using the median of a[p], a[(p+q) div 2], and a[q]. This is the method used in the file sort.c.