Quicksort: The Big Picture!
- Explain and trace the quicksort algorithm on a particular data sequence.
In Quicksort, we partition the sequence into two subsequences separated by a single element $x$ that is greater than or equal to every element in the left subsequence and less than or equal to every element in the right subsequence.
After partitioning, the element $x$, called the pivot element, is in its final (sorted) position.
We now apply the partitioning to the two subsequences separately. This process is naturally recursive (and quick).
Demo
Resources
- Wikipedia's entry on Quicksort.
- Baeldung's An Overview of QuickSort Algorithm.
- InterviewBit's Quicksort Tutorial with pictorial examples and a video explanation.
- Toptal's page on Quicksort with animation, code, analysis, and discussion.
- xSortLab demo on Quicksort (Along other sorts).