The Quicksort algorithm relies heavily on partitions. 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 that we’ll partition each subarray, and end up with even smaller subarrays to the left and right of each subarray’s pivot. We then partition those 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.
Below is a quicksort! method that we can add to the preceding SortableArray class that would successfully complete Quicksort:
|||def quicksort!(left_index, right_index)|
|||#base case: the subarray has ...|
Get A Common-Sense Guide to Data Structures and Algorithms 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.