Question

What is the reason to choose a random pivot element in Randomized Quicksort? How can using randomization in this way possibly help?

Answer 1

Your regular quicksort algorithm can trigger a worst case scenario with a time complexity of O(n2) when the input is already sorted. Let me explain with the help of an example:
Assume the input sequence to be 1,2,3,4,5,6,7,8,9,10.
Now, if you take 1 as your pivot element you will recursively sort 2,3,4….10.
In second pass, if you take 2 as your pivot element you will recursively sort 3,4,5…10.
In third pass, if you take 3 as your pivot element you will recursively sort 4,5,6….10 and so on.
In the first pass you are looking at n-1 elements, in the second pass you are looking at n-2 elements, in third pass you are looking at n-3 elements. For an input which is already sorted, the regular quicksort takes a lot of time for the program to completely execute.
In a randomised quicksort algorithm since you are randomly selecting a pivot point, there isn’t any just one input which can trigger a worst case scenario like in the above situation. The randomness of it all ensures an expected run time of O(n log n).
In addition to this, the quicksort algorithm is vulnerable to certain security threats like the DoS attack. Using randomised quicksort will less likely expose you to vulnerabilities like these.