Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 15 down vote accepted

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.

share|improve this answer
6  
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). –  SamM Dec 24 '12 at 21:30
    
When you say "distributed uniformly at random", you mean that each of the $n!$ permutations has equal probability of $\frac{1}{n!}$? –  Robert S. Barnes Apr 19 '13 at 5:50
    
@RobertS.Barnes Yes –  Jernej Apr 19 '13 at 10:37

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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