Consider this pseudocode for quicksort, which leaves pivot selection and partiti
ID: 3556521 • Letter: C
Question
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
Explanation / Answer
quicksort(int[] array, int lo, int hi, int enough) {
if (lo>=hi-1) return;
pivot = pickPivot(array,lo,hi);
pivotIndex = partition(array,lo,hi,pivot);
/* We need first enough numbers sorted from the first partition */
quicksort(array,lo,pivotIndex, enough);
/* If there are not enough numbers in the first partitions, then we need to sort the remaining numbers from the second partition */
if (enough > pivotIndex - lo + 1) {
quicksort(array,pivotIndex+1,hi, enough - (pivotIndex - lo + 1));
}
}