2012-05-03, 10:28 PM
1. Maybe you should paste their code here then.
2.3. The whole point is that quicksort is only fast when two partitions are roughly the same size. When you have a large number of duplicate values one partition will be much larger than the other, causing more recursive calls. In the case of the entire array being duplicates, it becomes the same as selection sort, i.e. O(n^2). You should be counting the number of comparisons there, not number of swaps.
When people discuss sorting algorithms, they generally assume there are no duplicate values.
2.3. The whole point is that quicksort is only fast when two partitions are roughly the same size. When you have a large number of duplicate values one partition will be much larger than the other, causing more recursive calls. In the case of the entire array being duplicates, it becomes the same as selection sort, i.e. O(n^2). You should be counting the number of comparisons there, not number of swaps.
When people discuss sorting algorithms, they generally assume there are no duplicate values.