18
$\begingroup$

In their book Randomized Algorithms, Motwani and Raghavan open the introduction with a description of their RandQS function -- Randomized quicksort -- where the pivot, used for partitioning the set into two parts, is chosen at random.

I have been racking my (admittedly somewhat underpowered) brains over this for some time, but I haven't been able to see what advantage this algorithm has over simply picking, say, the middle element (in index, not size) each time.

I suppose what I can't see is this: if the initial set is in a random order, what is the difference between picking an element at a random location in the set and picking an element at a fixed position?

Can someone enlighten me, in fairly simple terms?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
19
$\begingroup$

If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random.

If however your input array is not really in random order (which happens to be the case in almost all practical scenarios) then one needs to either "preshufle" the array in order for the elements in it to be placed in random order, or (equivalently) always take a random element as a pivot. This ensures the partitioning phase of quicksort partitions the arrays into sub-arrays of almost equal size and hence that the expected running time remains $O(n\log n)$

So your confusion appears to come from the fact that somehow you assume a sorting algorithm can (in practice) expect the input array to always be randomly distributed.

Improve this answer
$\endgroup$
3
  • 7
    $\begingroup$ It may be worth mentioning that while there's a theoretical guarantee to randomizing (because you get $O(n\log n)$ worst case instead of $O(n^2)$) prerandomizing data can lead to practical speedups as well in some applications. Bad quicksort cases are more common than one might expect (depending obviously on implementation). $\endgroup$
    – SamM
    Dec 24, 2012 at 21:30
  • $\begingroup$ When you say "distributed uniformly at random", you mean that each of the $n!$ permutations has equal probability of $\frac{1}{n!}$? $\endgroup$
    – Robert S. Barnes
    Apr 19, 2013 at 5:50
  • $\begingroup$ @RobertS.Barnes Yes $\endgroup$
    – Jernej
    Apr 19, 2013 at 10:37
4
$\begingroup$

As noted by Jernej, the assumption that the all permutations of the input are equally likely does not always hold in reality. The first idea might be to permute the input array. This would work, but is easier to analyze the situation where a pivot is chosen at random. This is also known as random sampling.

Improve this answer
$\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.