Quicksort Partition Logic Error
Consider the partition method provided in the FaultyPartition class. Which statement best describes a potential inefficiency or logical error in this method’s handling of elements that are equal to the pivot value?
public class FaultyPartition {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low;
int j = high;
while(i < j) {
while(i < high && arr[i] <= pivot) {
i++;
}
while(j > low && arr[j] > pivot) {
j--;
}
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
return j;
}
public static void main(String[] args) {
int[] row = {3, 8, 3, 5, 1, 4};
int index = partition(row, 0, row.length - 1);
for(int num : row) {
System.out.print(num + " ");
}
System.out.println("\nPivot index: " + index);
}
}
A
It incorrectly swaps elements during partitioning, leading to data corruption.
B
It does not correctly group elements equal to the pivot due to using a strict ‘>’ condition in the second inner loop, which can lead to unbalanced partitions.
C
It chooses the pivot from the end of the array, which always causes worst-case performance.
D
There is no inefficiency; the method handles duplicates perfectly.
Question Leaderboard
Not enough data yet to show leaderboard.
APFIVE