O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Quicksort

The Quicksort algorithm relies heavily on partitions. It works as follows:

  1. Partition the array. The pivot is now in its proper place.

  2. 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.

  3. 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required