A pivot is an element chosen from a sequence to divide the remaining elements during partitioning. In quicksort, elements smaller than the pivot go into one sub-array, while larger elements go into another. section 4.2
A quicksort walkthrough
For [10, 15, 33], choosing 33 as the pivot leaves [10, 15] on the left and an empty sub-array on the right. Quicksort sorts both sub-arrays, then combines left array + pivot + right array. Choosing 15 instead produces two one-element sub-arrays, reaching the base case sooner. section 4.2 section 4.5
A pivot guides quicksort through three steps:
- Pick an element as the pivot. section 4.2
- Partition the other elements into sub-arrays according to their relationship to the pivot. section 4.2
- Apply quicksort recursively to the sub-arrays, then place the pivot between the sorted results. section 4.2
The choice matters because partitioning touches O(n) elements at each level. Balanced partitions create O(log n) levels and O(n log n) time; repeatedly choosing a poor pivot can create O(n) levels and O(n²) time. Choosing a random element gives O(n log n) time on average, except that an all-equal array still needs additional logic. section 4.3 section 4.5
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
Inspect a compact Python implementation showing pivot selection, partitioning, recursive calls, and the base case. section 4.2
