5
$\begingroup$

This CodeGolf answer suggests that quick sorting an array whose elements can take only two values is linear. Can this assumption be proved?

$\endgroup$
  • 2
    $\begingroup$ First of all, "QuickSort" isn't actually an algorithm, it's a family of algorithms depending upon how you pick the pivot, and how you divide equal elements. The answer here will strongly depend upon those choices. It's not too hard to see that choosing poorly will still result in $O(n^2)$ worst-case behavior. Whether you can do better isn't as clear. $\endgroup$ – Mark Reitblatt Feb 4 '11 at 21:34
  • 4
    $\begingroup$ The standard implementation of quicksort should never be linear ... the best possible running time would be $n \log_2 n$. $\endgroup$ – Peter Shor Feb 4 '11 at 21:46
  • 7
    $\begingroup$ I think the answer is something like is. All elements are either 1 or 2. Pick your pivot arbitrarily. After the scanning phase, you're automatically sorted. $\endgroup$ – Suresh Venkat Feb 4 '11 at 22:03
  • 2
    $\begingroup$ If you exclude elements equal to the pivot from the recursion, you end at depth 2. But I don't think that's the standard version. $\endgroup$ – Marcus Ritt Feb 4 '11 at 22:56
  • 3
    $\begingroup$ @Suresh: yes, but the usual algorithm doesn't detect this. $\endgroup$ – Marcus Ritt Feb 4 '11 at 23:25
20
$\begingroup$

There is a large body of research on Quicksort for sorting multisets. The talk Quicksort is optimal by Sedgewick gives a nice overview of this. Basically with 3-way partitioning you get within a constant of the information theoretic minimum. The information theoretic minimum is: Suppose we are to sort $n$ keys, where there is only $m$ distinct keys, and the $i$th key occurs $n_i$ times. Then we need $n \lg(n) - \sum_{i=1}^m n_i\lg n_i -n \lg e +O(\lg n)$ three way comparisons on the average. (See "Sorting multisets and vectors in-place", by Munro and Raman).

$\endgroup$
  • $\begingroup$ excellent. that's a great answer. $\endgroup$ – Suresh Venkat Feb 5 '11 at 18:32
6
$\begingroup$

Depends on the exact implementation.

If you check for already-sorted arrays, then qsort stops after the initial pass, so is O(n).

If, as Marcus suggested, you perform a three-way partition into x<pivot, x=pivot, and x>pivot and don't sort the middle partition, then the recursion stops at a depth of 2, and so is still O(n).

If you don't check for already-sorted arrays and don't exclude elements equal to the pivot from recursion, then the number of elements to sort only decreases by 1 every time, so your qsort would be O(n²).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.