I was trying to learn quick sort algorithm. I found a blog post which helped me understand the concept & time complexity of quick sort Quick Sort Implementation In Java – W3 Spot. But it uses right most element for pivot selection in the example given. It says there are better ways to select pivot, but they were not part of the post. I understood why pivot selection algorithm is important as the blog post clearly shows it with two different examples. I just want to know what is the popular algorithm that most people use & where can I learn it.
Honestly, the best algorithm is the one that someone else has written and tested and is fast enough for your needs.
It can be useful to learn, but rarely will you roll your own sort algorithm, except as a learning process.
The “most popular” doesn’t mean the right one. Deciding the pivot usually is done for the furthest left/right item in the array depending on the “best case scenario” if the array is already sorted. As if its already sorted, then you’d want quicksort to not “re-sort” everything as that hurts your best case speed.
If the data is 100% random, and never is pre-sorted then it doesn’t actually matter. In practice there may be some patterns you could leverage but again its all situational.
Finally the choice of what the best pivot is isn’t an algorithm, its just a choice in itself for you to choose based on the data you’re working with.
Thanks @bradtaniguchi for explaining it.