P14.10 Bentley and McIlroy suggest the following modification to the quicksort a
ID: 652855 • Letter: P
Question
P14.10 Bentley and McIlroy suggest the following modification to the quicksort algorithm when dealing with data sets that contain many repeated elements. Instead of partitioning as = (where leq denotes the elements that are s the pivot), it is better to partition as Sorting and Searching However, that is tedious to achieve directly. They recommend to partition as = = and then swap the two = regions into the middle. Implement this modification and check whether it improves performance on data sets with many repeated elementsExplanation / Answer
void quickSort(int[] data, int first, int last){
if (first >= last)
return;
int pivot = partition(data, first, last);
/* sort the left part */
quickSort(data, first, pivot - 1);
/* sort the right part */
quickSort(data, pivot + 1, last);
}
int partition(int[] data, int first, int last){
int pivot = data[first];
int left = first, right = last;
while (left < right){
// Find an element bigger than the pivot from the left
while (data[left] <= pivot && left < right)
left++;
// Find an element smaller than the pivot from the right
while (data[right] > pivot)
right--;
// Swap the two elements found
if (left < right)
swap(data, left, right);
}
// move the pivot element to the middle
swap (data, first, right);
return right;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.