Quicksort: How to choose the pivot (Animated!)
If you don't understand pivot selection in depth, you don't know quicksort. Using colorful sorting animations, this video explains the advantages and disadvantages of multiple methods of choosing pivots in the quicksort algorithm. It's a great way to review quicksort for those who have seen it before or to go more in depth for those learning quicksort for the first time now. Thinking through the various pivot selection strategies will help you prepare for job interviews or help you study for a DSA/data structures and algorithms course. As always, colorful sorting animations (written in Python/ManimCE) accompany thorough explanations.
If you like my teaching style, I offer private tutoring:
https://www.codeslatetutoring.com/fro...
References:
Engineering a Sort Function (info on pseudomedian of 9/Tukey's ninther):
https://gallium.inria.fr/~maranget/X/...
Details on proof of correctness for quicksort: See CLRS algorithms Chapter 7
Use of special algorithm to find median each time (MIT lecture, relevant info starts at about 1:02:30):
• 6. Randomization: Matrix Multiply, Quicksort
Stack overflow post with median of 3 killer:
https://stackoverflow.com/questions/2...
Paper on introsort and median-of-3-killer:
https://webpages.charlotte.edu/rbunes...