• In the randomized version of Quick sort we impose a distribution on input.
• This does not improve the worst-case running time independent of the input ordering.
• In this version we choose a random key for the pivot.
• Assume that procedure Random (a, b) returns a random integer in the range [a, b); there are b-a+1 integers in the range and procedure is equally likely to return one of them.

• The new partition procedure, simply implemented the swap before actually partitioning.

• RANDOMIZED_PARTITION (A, p, r)

  $\hspace{1cm}$ i ← RANDOM (p, r)

  $\hspace{1cm}$ Exchange A[p] ↔ A[i]

  $\hspace{1cm}$ return PARTITION (A, p, r)

• Now randomized quick sort call the above procedure in place of PARTITION

• RANDOMIZED_QUICKSORT (A, p, r)

  $\hspace{1cm}$If p < r then

  $\hspace{1.3cm}$q ← RANDOMIZED_PARTITION (A, p, r)

  $\hspace{1.3cm}$ RANDOMIZED_QUICKSORT (A, p, q)

  $\hspace{1.3cm}$ RANDOMIZED_QUICKSORT (A, q+1, r)

• Like other randomized algorithms, RANDOMIZED_QUICKSORT has the property that no particular input elicits its worst-case behavior.

• The behavior of algorithm only depends on the random-number generator. Even intentionally, we cannot produce a bad input for RANDOMIZED_QUICKSORT unless we can predict generator will produce next.

Complexity of Randomized Quick Sort

• If we have an array of equal elements, the array index will never increment i or decrement j, and will do infinite swaps. i and j will never cross.

• Worst Case: O(N^2)

  This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.

• Worst-case Running Time

  The worst case for quick-sort occurs when the pivot is the unique minimum or maximum element. One of L and G has size n - 1 and the other has size 0 The running time is proportional to the sum (n + (n - 1) + … + 2 + 1) Thus, the worst-case running time of quick-sort is O (N^2)

  Depth time

  0 N

  1 n - 1

  … …

  n – 1 1

• Worst-Case Analysis

  The pivot is the smallest (or the largest) element

  T (N) = T (N-1) + cN, N > 1

  Telescoping:

  T (N-1) = T (N-2) + c (N-1)

  T (N-2) = T (N-3) + c (N-2)

  T (N-3) = T (N-4) + c (N-3)

  ……………………………..

  T (2) = T (1) + c.2

  T (N) + T (N-1) + T (N-2) + … + T (2) =

  = T (N-1) + T (N-2) + … + T (2) + T (1) +

  C (N) + c (N-1) + c (N-2) + … + c.2

  T (N) = T (1) + c times (the sum of 2 thru N)

  = T (1) + c (N (N+1) / 2 -1) = O (N2)

• Average-case: O (N logN)

• Best-case: O (N logN)

  The pivot is the median of the array, the left and the right parts have same size. There are logN partitions, and to obtain each partition we do N comparisons (and not more than N/2 swaps). Hence the complexity is O (NlogN).

• Best case Analysis:

  T (N) = T (i) + T (N - i -1) + cN

  The time to sort the file is equal to the time to sort the left partition with i elements, plus the time to sort the right partition with N-i-1 elements, plus the time to build the partitions.

  The pivot is in the middle

  T (N) = 2 T (N/2) + cN

  Divide by N: T (N) / N = T (N/2) / (N/2) + c

  Telescoping:

  T (N) / N = T (N/2) / (N/2) + c

  T (N/2) / (N/2) = T (N/4) / (N/4) + c

  T (N/4) / (N/4) = T (N/8) / (N/8) + c

  ……

  T (2) / 2 = T (1) / (1) + c

  Add all equations:

  T (N) / N + T (N/2) / (N/2) + T (N/4) / (N/4) + …. + T (2) / 2 =

  = (N/2) / (N/2) + T (N/4) / (N/4) + … + T (1) / (1) + c.logN

  After crossing the equal terms:

  T (N)/N = T (1) + c * LogN

  T (N) = N + N * c * LogN = O (NlogN)