Quicksort
The Quicksort algorithm is a combination of partitions and recursion. It works as follows:
-
Partition the array. The pivot is now in its proper place.
-
Treat the subarrays to the left and right of the pivot as their own arrays, and recursively repeat Steps 1 and 2. That means we’ll partition each subarray and end up with even smaller sub-subarrays to the left and right of each subarray’s pivot. We then partition those sub-subarrays, and so on and so forth.
-
When we have a subarray that has zero or one elements, that is our base case and we do nothing.
Let’s return to our example. We began with the array of [0, 5, 2, 1, 6, 3] and ran a single partition on the entire array. Since Quicksort begins with such a partition, that means we’re ...
Get A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
