DSA Quicksort
Quicksort is a sorting method that splits a list around a pivot, one chosen value as the split point. Values smaller than the pivot go left and larger values go right.
One partition
Partitioning is splitting values by comparison with the pivot. This code uses three groups, so equal values stay together in the middle group.
values = [9, 3, 7, 5, 8, 2]
pivot = values[len(values) // 2]
smaller = []
same = []
larger = []
for value in values:
if value < pivot:
smaller.append(value)
elif value > pivot:
larger.append(value)
else:
same.append(value)
print("pivot:", pivot)
print("smaller:", smaller)
print("same:", same)
print("larger:", larger)Quicksort in full
Quicksort partitions each side again with its own pivot. A list of zero or one value needs no partitioning at all.
def quicksort(values):
if len(values) <= 1:
return values
pivot = values[len(values) // 2]
smaller = [v for v in values if v < pivot]
same = [v for v in values if v == pivot]
larger = [v for v in values if v > pivot]
return quicksort(smaller) + same + quicksort(larger)
print(quicksort([9, 3, 7, 5, 8, 2]))A poor pivot on sorted data
A pivot at the edge of sorted data splits off only one value. That lopsided split leaves almost all the work for the later calls.
values = [1, 2, 3, 4, 5, 6]
pivot = values[0]
smaller = [v for v in values if v < pivot]
larger = [v for v in values if v > pivot]
print("pivot:", pivot)
print("smaller size:", len(smaller))
print("larger size:", len(larger))Example
def quicksort_count(values, pick_first, counter):
if len(values) <= 1:
return values
counter[0] += len(values)
if pick_first:
pivot = values[0]
else:
pivot = values[len(values) // 2]
smaller = [v for v in values if v < pivot]
same = [v for v in values if v == pivot]
larger = [v for v in values if v > pivot]
left = quicksort_count(smaller, pick_first, counter)
right = quicksort_count(larger, pick_first, counter)
return left + same + right
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
counter = [0]
result = quicksort_count(data, False, counter)
print("middle pivot:", result)
print("middle pivot checks:", counter[0])
counter = [0]
result = quicksort_count(data, True, counter)
print("first pivot:", result)
print("first pivot checks:", counter[0])Key points
- Quicksort sorts each side of a partition on its own.
- The pivot choice decides how even the split is.
- An edge pivot on sorted data makes one side shrink by one value only.
- A middle pivot splits sorted data into two near halves.
In this example, quicksort sorts a list that is already in order, in two different ways. Each value checked against a pivot counts as one check. The middle pivot splits the sorted data into near halves, and the checks stay low. The first value is the smallest value, so each partition splits off just one value. That poor choice spends far more checks on exactly the same final answer.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
Quicksort partitions the list [9, 3, 7, 5, 8, 2] around the middle value 5. Which group holds the values smaller than the pivot?