Need to sort an array? Quicksort breaks the job into smaller sorting jobs. Pick one element, called the pivot, and partition the remaining elements around it. Sort each partition the same way, then join the results with the pivot in the middle. section 4.2 section 4.0
Sort three numbers
To sort [33, 15, 10], choose 33 as the pivot. The smaller partition is [15, 10], and the larger one is empty. Sort the smaller partition, then combine [10, 15] + [33] + [] to get [10, 15, 33]. section 4.2
The same steps work for longer arrays:
- Return an empty array or a one-element array unchanged. That is the base case. section 4.2
- Choose a pivot and put the other elements into two partitions. The Python example puts values equal to the pivot in the smaller-side partition. section 4.2
- Call quicksort on both partitions and combine the sorted results with the pivot. section 4.2
Does the pivot matter? Yes. A first-element pivot on an already sorted array leaves one partition empty at every step, producing O(n²) time and an O(n)-deep call stack. Balanced partitions take O(n log n) time and use an O(log n)-deep stack. A random pivot gives O(n log n) average time, though arrays whose elements are all equal need additional logic to avoid the worst case. section 4.5 section 4.3
def quicksort(array):
if len(array) < 2:
return array #1
else:
pivot = array[0] #2
less = [i for i in array[1:] if i <= pivot] #3
greater = [i for i in array[1:] if i > pivot] #4
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
#1 Base case: arrays with 0 or 1 element are already sorted.
#2 Recursive case
#3 Sub-array of all the elements less than the pivot
#4 Sub-array of all the elements greater than the pivot
The Python listing puts the base case, both partitions and recursive combination together in one short implementation. section 4.2
