Use Jon Bentleys Quicksort algorithm to sort the following array:

| 5 | 3 | 2 | 8 | 1 | 0 | 6 | 7 | 4 |

However, to choose the pivot element, dont simply pick the first element of the partition being sorted. Instead, use the median-of-3 rule, that is, for your pivot element for the current partition, choose the median of: {first element, middle element, last element} where the middle element of this partition is defined as follows:

If i is the subscript of the first element, and j is the subscript of the last element, then the subscript of the middle element is k = ceiling((i + j) / 2).

Thus, for the first call, the subscripts are i = 0, j = 8, and k = ceiling((0 + 8) / 2) = 4; therefore, we take the median of the three values 5, 1, and 4which in this case is the value 4. This means the last element (4) gets swapped with the first element (5) before starting the Quicksort algorithm. Note that this operation is done in O(1) time and does not affect the complexity of Quicksort.

For your answer to this question, show the results of each call to qsort, and what the next call would be. In other words, trace the execution. Its up to you as to whether you show the trace table or not.

quicksort by jon bentley:

void qsort(int x[], int lo, int hi) {

int i, p; if

(lo >= hi) return; p = lo; for( i=lo+1; i <= hi; i++ )

if( x[i] < x[lo] ) swap(x[++p], x[i]);

swap(x[lo], x[p]);

qsort(x, lo, p-1);

qsort(x, p+1, hi);

}

void quicksort(int x[], int n) {

qsort(x, 0, n-1);

}