Hoare Partition Scheme Pivot Selection
Consider the following partition method, which implements Hoare’s partitioning scheme. Which of the following describes a significant performance pitfall of this implementation?
public class Sorter {
public int partition(int[] data, int low, int high) {
int pivot = data[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (data[i] < pivot);
do {
j--;
} while (data[j] > pivot);
if (i >= j) return j;
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
A
Initializing i and j in this way inevitably leads to an infinite loop regardless of the input.
B
The pivot is updated inside the loop, causing its value to change and lead to incorrect partitioning.
C
The do-while loops might skip elements equal to the pivot, resulting in an unbalanced partition.
D
Choosing the first element as the pivot can lead to poor performance on nearly sorted arrays or arrays with many duplicates.
Question Leaderboard
Not enough data yet to show leaderboard.
