CS201: Elementary Data Structures

7.7: Quicksort

• Massachusetts Institute of Technology: Erik Demaine and Charles Leiserson's "Quicksort and Randomized Algorithms" Page

  Watch this lecture until 18:44 for an explanation of Quicksort. If you watch through the end, you will be led through a deep analysis that derives Big-O for this algorithm.
  

• Crazy for Code: "Recursive Quicksort in C++" Page

  This recursive implementation of quicksort in C++ closely mirrors the one discussed in the lecture, which used Python.
  

• Remi Dufour's "Non-recursive Quicksort in C++" Page

  This is a non-recursive version of Quicksort for C/C++. The variable "recursive" is used to show where recursion would normally take place. We present this since the lectures in this unit use Python for illustration.