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’s 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 already ...
Get A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1 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.
