Quick Sort - Why Random Pivot?

1
votes

After looking at different quick sort algorithms:

I'm not seeing the benefit(s) to using a random pivot. Compared to using the last element, and recursively calling quickSort(a[], int p, int r), does selecting the pivot randomly increase efficiency?

Thx

1
algorithmsortingquicksort
Yes, it does. Random pivoting reduces the chance of hitting the worst case, especially for data that is fully or almost reversed - Marcin
Refer this geeksforgeeks.org/when-does-the-worst-case-of-quicksort-occur - bigbounty
Makes sense, thank you - Log_Thor

1 Answers

0
votes

The reason to use random pivoting is that of not allowing adversary to make your algorithm hit worst case time. In other words with random pivoting your algorithm expected performance equally good on all datasets.