Randomized Quicksort

If you assume all permutations of the numbers are equally likely when choosing the "divider" T (n) = Q (n lg n) , we are in the average case. If we cannot assume all permutations are equally likely, we must enforce it.

Random ( a, b ) returns integer , x, ' a £ x £ b It is implemented with a pseudorandom number generator. http://sprng.cs.fsu.edu has lots of PRNG's.

The randomized quicksort algorithm uses i ¬ Random ( A, p, r ) to be the new pivot element.

Randomized-Partition ( A, p, r )

1. i ¬ Random ( p, r )

2. exchange A[p] « A[i]

3. return Partition ( A, p, r )

Randomized-Quicksort ( A, p, r )

1. If p < r

2.      then q ¬ Randomized-Partition ( A, p, r )

3.            Randomized-Quicksort ( A, p, q )

4.            Randomized-Quicksort ( A, q+1, r )