# Handling duplicate keys in quicksort

A naïve quicksort will take O(n^2) time to sort an array containing no unique keys, because all keys will be partitioned either before or after the pivot value. There are ways to handle duplicate keys (like one described in Quicksort is Optimal). The proposed solution only works for the Hoare partition, but I've implemented the Lomuto partition. To deal with duplicate keys, I alternated between moving duplicates to the left of the pivot and moving duplicates to the right of the pivot. Here's my quicksort (ignore the lack of generics):

public static void swap(Comparable[] sort, int a, int b){
Comparable temp=sort[a];
sort[a]=sort[b];
sort[b]=temp;
}
public static void quicksort(Comparable[] sort, int start, int end){
while(end-start>1){//normal case
int pivot=gen.nextInt(end-start)+start;//random pivot
swap(sort, pivot, start);
int index=start;//walking index
boolean dupHandler=false;//init to true works also
for(int i=start+1; i<end; ++i){//Lomuto partition
int val=sort[start].compareTo(sort[i]);
if(val>0 || ( val==0 && (dupHandler=!dupHandler) ) )
swap(sort, ++index, i);
}
swap(sort, start, index);
if(index-start<end-index-1){//recurse into smaller partition
quicksort(sort, start, index);
start=index+1;//use iteration for other partition
}
else{
quicksort(sort, index+1, end);
end=index;
}
}
}


Is there a better (more efficient) way to handle duplicate keys? If not, is there any way to significantly improve my code?

• This is code review, not pseudocode review. If you want reviews of your code, please post your actual code. – Winston Ewert Aug 5 '11 at 4:02
• Naive quicksort is O(n^2) full stop; it has nothing to do with duplicate keys. – Rafe Aug 5 '11 at 4:56
• @Winston Code is posted – Derek Aug 5 '11 at 5:02
• @Rafe I know, but even a quicksort with random pivot selection will degenerate to the O(n^2) case if all keys are equal. – Derek Aug 5 '11 at 5:07
• Consider sorting an ascending list of numbers. To guarantee O(n log n) you do quicksort for the first k log n levels of recursion, then back off to a guaranteed O(n log n) sort, albeit with a larger constant factor than quicksort (e.g., merge sort). – Rafe Aug 5 '11 at 5:10

1. Use a swap function rather then repeating the three lines required to swap elements three times
2. Put spaces around your operators
3. You avoid recursing for the second partition. I don't think the performance gain from this is sufficient for the extra complexity in your code.

Rather then swapping before/after for the element equal to the pivot, count the number of elements equal to the pivot. Then when you sort the subarray make the one subarray shorter so as not to sort the elements equal to the pivot.

Another issue as Rafe has noted is that there are other issues besides duplicate keys that can cause a O(n^2) behavior. Your code doesn't handle any of those.

• 1. I just changed the code inside the loop so that the lines aren't repeated. Is that better or worse than before? 2. Too lazy to do that now, but you're right 3. The added complexity doesn't seem like much to me; it's just one extra if-else statement 4. I like that way of handling duplicates, I'll implement it when it's not 2AM 5. I do choose a random pivot... the only more efficient pivot choices are the median-of-three (still no O(nlogn) guarantee) and the O(n) selection algorithms (these esnure O(nlogn) time but increase those pesky constant factors) – Derek Aug 5 '11 at 5:54
• I don't know how to put newlines in comments... sorry 'bout that – Derek Aug 5 '11 at 5:55
• @Derek, 1. you are still repeating the swap code three times. 3. There is also the while loop (which would be an if statement) but just generally your code obscures the nature of the quicksort algorithm. 5. Choosing a random pivot is good, but that doesn't guarantee you won't have problems. You could randomnly choose bad pivots. – Winston Ewert Aug 5 '11 at 6:07
• 1. OH RIGHT... I forgot about the other swaps... 3. The complexity of the code is of no concern, so long as I can understand it; I'm coding this for fun (yes, I do that) 5. I'm open to any pivot-selection algorithms; any one in particular that you recommend? – Derek Aug 5 '11 at 6:12
• @Derek, 3. This is code review, I reserve the right to complain that your code has been made less readable for probably undetectable performance gains. You can reserve the right to ignore me. :) 5. I'm not suggesting a better pivot selection algorithm. I'm wondering whether your strategy has any advantage over something like introsort. – Winston Ewert Aug 5 '11 at 6:22