QuickSort Partition With Duplicate Elements
What is a potential drawback of the partition implementation shown below when the input array contains a large number of duplicate elements?
public class QuickSortEqualPivot {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
}
A
It swaps the pivot element multiple times unnecessarily, making the sort unstable.
B
It can lead to unbalanced partitions, degrading QuickSort’s performance.
C
It produces an incorrect sorted order because duplicates are not correctly compared.
D
It will cause an ArrayIndexOutOfBoundsException due to duplicate values.
Question Leaderboard
| Rank | |||||
|---|---|---|---|---|---|
| #1 | lightingstrikes1342 | 2 | 2 | 0m 00s | 200 |
| #2 | znasibli1 | 0 | 1 | 0m 00s | -10 |
| #3 | mavericklin125 | 0 | 2 | 0m 00s | -20 |
Items per page:
10
1 – 3 of 3
APFIVE