3
$\begingroup$

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.

After reading this document it shows that worse case partitions are of the type $(0,(n-1)), (0,(n-2)), (0,(n-3))$ and so on. So the work on every step is $Cn, C(n-1), C(n-2)$ , it actually decreases since $C(n) > C(n-1)$. Correct me if I am wrong.

While in best case the partitions on every step can be assumed as $n/2$ on each side or $n/2$ or $n/2 - 1$ on each side. So the work done on each step, is $Cn$ always.

So how is that better than unbalanced partitions ? The work actually decreases in every step for unbalanced partitions, while for balanced partitions the work actually remains constant on all the steps and depending on the partition algo it may even include the pivot which is already sorted.

$\endgroup$
4
$\begingroup$

for balanced partitions the work actually remains constant on all the steps

That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the current one.

You also seem to be missing that, for the total cost, you need to add up all the steps. Just saying, "the inputs get smaller", doesn't tell you anything besides that the algorithm terminates.

In the worst case, you get the solution of a recurrence similar to

$\qquad\begin{align*} T(1) &= 0 \\ T(i) &= T(i-1) + i \end{align*}$

which solves to some $T \in \Theta(n^2)$.

In the average case, you get the solution of a recurrence similar to

$\qquad\begin{align*} T(1) &= 0 \\ T(i) &= 2T(i/2) + i \end{align*}$

which solves to some $T \in \Theta(n \log n)$.


To stress my point from above, consider

$\qquad\begin{align*} T(1) &= 0 \\ T(i) &= T(i/2) + i \end{align*}$

which solves to some $T \in \Theta(n)$.

Or

$\qquad\begin{align*} T(1) &= 0 \\ T(i) &= T(i/2) + 1 \end{align*}$

which solves to some $T \in \Theta(\log n)$.

You see that the specifics of the recurrence matter.

$\endgroup$
  • $\begingroup$ 'each recursive call gets an input that is properly smaller than the current one.' That's true but when you add up the amount of work done at any level it is still equal to $Cn$ $\endgroup$ – ng.newbie Aug 16 '17 at 8:16
  • $\begingroup$ @ng.newbie Yes. It wasn't clear to me from your question that that was your issue (you used "step" instead of "level"). See Louis' answer! (Actually, no; it's not equal to $Cn$; the pivots do get picked out! Otherwise, Quicksort wouldn't terminate.) $\endgroup$ – Raphael Aug 16 '17 at 8:54
  • $\begingroup$ Take the input sequence 4,5,3,2,1. If 3 is selected as the pivot and (Hoare's original partition) [en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme] scheme is used then i and j meet at the same point. Then the partition becomes 1,2,3 and 4,5. The pivot is still there in one of the partition. Ideally the resultant partitions should be 1,2 and 4,5 $\endgroup$ – ng.newbie Aug 16 '17 at 10:53
  • $\begingroup$ @ng.newbie I stand corrected. (Although I have little confidence in Wikipedia being accurate...) You should specify that that is the partitioning method you want to investigate. $\endgroup$ – Raphael Aug 16 '17 at 11:36
  • $\begingroup$ @ng.newbie You may find this one interesting. $\endgroup$ – Raphael Aug 16 '17 at 11:38
3
$\begingroup$

Raphael's answer gives you a formal proof: the recurrence from using a balanced partition solves to $\Theta(n \log n)$ and the (arbitrarily) unbalanced one to $\Theta(n^2)$.

Quicksort's recursive structure is nice enough that we can get a lot of intuition from looking at the recursion tree. Every level of recursive calls is just a partition (into a growing number of parts) of the $n$ elements of the original input. Every element not in a cell of size one is compared as a non-pivot at each level.

This tells us that as long as there are $\delta n$ elements in a non-trivial sub-problem (in total, there may be many non-trivial problems left) at some level, Quicksort makes about $\delta n$ comparisons.

It's then easier to see that the best partitioning scheme will minimise the total number of levels. Balanced partitioning gives you $\Theta(\log n)$ of them, and so a total running time of $\Theta(n\log n)$.

This kind of accounting is the idea underlying a very useful lemma by Timothy Chan for analysing recursive algorithms.

$\endgroup$
  • $\begingroup$ "Quicksort makes about δn comparisons." -- "about" is crucial here. Different partitioning algorithms have different cost. $\endgroup$ – Raphael Aug 16 '17 at 8:57
  • $\begingroup$ "It's then easier to see that the best partitioning scheme will minimise the total number of levels. " -- fun fact: this is not universally true. I'm not sure about standard Quicksort, but for dual-pivot QS with Yaroslavskiy partitioning (and generalizations) it's not true: uneven splits are better! See the work of Sebastian Wild for details. $\endgroup$ – Raphael Aug 16 '17 at 8:58
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Raphael Aug 16 '17 at 9:30
  • $\begingroup$ @Louis Could you please explain what you mean by 'δn elements' ? $\endgroup$ – ng.newbie Aug 16 '17 at 11:02
  • $\begingroup$ @Louis What do you mean by 'Every element not in a cell of size one is compared as a non-pivot at each level.' ? Does that mean every partition that is not of size 1 is partitioned according to its pivot ? $\endgroup$ – ng.newbie Aug 16 '17 at 11:05

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.