P14.5 Bentley and Mcllroy suggest the following modification to the quicksort al
ID: 3717108 • Letter: P
Question
P14.5 Bentley and Mcllroy suggest the following modification to the quicksort algorithm when dealing with data sets that contain many repeated elements. Instead of partitioning as S 2 where s denotes the elements that are s the pivot), it is better to partition as 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 elements.Explanation / 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.