This video is part of Professor Frank Stajano’s lecture course on Algorithms at the University of Cambridge.
Quicksort is one of the most famous, most commonly used and most thoroughly studied sorting algorithms, primarily owing to the fact that it generally lives up to its name. It is therefore quite remarkable that its worst-case asymptotic complexity is in fact quadratic. But this worst case only occurs relatively rarely and therefore quicksort is widely adopted in practice, even in preference to algorithms whose worst case cost is O(n lg n) but with a larger constant in front, hidden by the O() notation.
A number of ingenious variants of quicksort have been devised, whether to make it go even faster or to reduce the probability that it will hit its worst case. One particularly cute variation uses the pivot strategy of quicksort for finding the 24th smallest element out of 1000 (or the k-th out of n, in the general case), using only linear time; except that this method too is subject to a rarely-encountered quadratic worst case.
We also introduce the notion of stability of a sorting algorithm. Quicksort is not stable, but I explain how to turn any unstable sorting algorithm into a stable one.
If you like this video, give it a thumbs up. Subscribe and hit the notification bell for more of the same and to encourage me to publish more videos for budding computer scientists. Leave your comments below.
Course web page:
https://www.cl.cam.ac.uk/teaching/current/Algorithms/
Course handout:
https://www.cl.cam.ac.uk/teaching/2021/Algorithms/2020-2021-stajano-algs-handout.pdf
My home page:
http://frank.stajano.com
Add comment