Partitioning splits an array around a chosen pivot, grouping other elements by comparison with it. In quicksort, the resulting groups are sorted recursively and joined with the pivot. section 4.2
To partition as part of quicksort:
- Choose a pivot from the array. section 4.2
- Group the remaining elements by comparing them with the pivot. section 4.2
- Sort each group recursively, then combine the sorted groups with the pivot. section 4.2
A pivot divides an array
For [10, 5, 2, 3], the code chooses 10 as the pivot and places 5, 2, and 3 in the lower group; the greater group is empty. section 4.2
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
Python quicksort code shows the base case, pivot choice, group construction, and recursive calls. section 4.2
