Randomized Quicksort

Question

Two ways to implement randomized Quicksort,

Method1: Choosing a random pivot

Method2: Generating a random permutation of the input and feeding it to a quicksort that chooses the first element as pivot

Is method1 same as method2 in terms of randomization?

Note: Looks like Method2 produces all partitions equally likely but method1 does not. So if they are not the same, then I want to understand what the performance impact is.

Answer 1

Yes. In either case, the probability of any particular element being selected as the pivot is 1/len(input). (However, the second method is almost certainly slower by a constant factor, since it will require an extra linear pass to generate the random permutation.)