QuickSort Partition With Duplicate Values
In the above QuickSort partition implementation, what potential issue might arise when the array contains duplicate values?
public class QuickSortPartition {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low;
int j = high - 1;
while(i < j) {
while(arr[i] < pivot) {
i++;
}
while(arr[j] > pivot) {
j--;
}
if(i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i];
arr[i] = arr[high];
arr[high] = temp;
return i;
}
public static void main(String[] args) {
int[] numbers = {3, 9, 4, 8, 5, 7, 6};
int pos = partition(numbers, 0, numbers.length - 1);
System.out.println("Pivot position: " + pos);
System.out.println(java.util.Arrays.toString(numbers));
}
}
A
The use of nested while loops causes some elements to be skipped during comparison.
B
The pivot is improperly swapped with the last element, which is never compared.
C
The pivot is selected as the first element instead of a randomized element, leading to poor performance.
D
The code does not properly handle elements equal to the pivot, potentially resulting in an incorrect partition.
Question Leaderboard
Not enough data yet to show leaderboard.
APFIVE