Consider this pseudocode for quicksort, which leaves pivot selection and partitioning to helper functions not shown:
// sort positions lo through hi-1 in array using quicksort (no cut-off) quicksort(int[] array, int lo, int hi) {
if (lo>=hi-1) return;
pivot = pickPivot(array,lo,hi);
pivotIndex = partition(array,lo,hi,pivot); quicksort(array,lo,pivotIndex); quicksort(array,pivotIndex+1,hi);
}
Modify this algorithm to take an additional integer argument enough:
// sort at least enough positions of lo through hi-1 in array using quicksort // (no cut-off)
quicksort(int[] array, int lo, int hi, int enough) { ... }
We change the definition of correctness to require only that at least the first 'enough' entries (from left-to right) are sorted and contain the smallest 'enough' values. (For example, if you are passed enough =5, then the 5 smallest values in the array should be located in locations 0-4 of the array. If enough >= hi-lo, then the whole range must be sorted as usual.) While one correct solution is to ignore the enough parameter and sort the entire array, come up with a better solution that skips completely unnecessary recursive calls. Assume the initial call to quicksort specifies that 'lo' is 0 and 'hi' is the upper-bound of the array. Watch your off-by-one errors!