1
$\begingroup$

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of unique numbers into $k$ classes? My goal is to demonstrate that this multiary partitioning can be achieved in $O(n \log k)$ time, ensuring that all classes are approximately of the same size (to within 1).

I found this paper https://cs.stanford.edu/~rishig/courses/ref/l11a.pdf

but it doesn't seem to talk about how to go about partitioning the array into nearly equal. Note: I am just interested in selecting the pivots not the partition algorithm

I did try finding the $n/k^{\text{th}}, 2n/k^{\text{th}} \ldots$ smallest element in the array and using them as pivots but the complexity isn't coming right (as each element can be found using BFPRT algorithm in $O(n)$ therefore total complexity would be $O(nk))$
Any Insights will be appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hint: Suppose $k$ is a power of two at first, for simplicity. Find the $n/2$th element in the array. Then.... (you fill in the next part)

$\endgroup$
3
  • 1
    $\begingroup$ if i follow u correclty the algo should be : Suppose k is a power of two at first, for simplicity. Find the n/2th element in the array. which is basically the middle element after partition then we find the middle element in both the arrays and so on. but won't the recurrence equation for the algo be T(n) =2T(n/2)+theta(n) which is theta( nk) as their will be k levels for the tree, where did i go wrong? $\endgroup$ Feb 17 at 12:30
  • 1
    $\begingroup$ @HaaziqJamal You went wrong in the number of levels. There will be only $O(\log k)$ levels (in each recursive call, you halve the number of pivots you are looking for). $\endgroup$
    – Tassle
    Feb 17 at 13:13
  • 1
    $\begingroup$ @Tassle ahh got it thanks $\endgroup$ Feb 17 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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