Medium Partition Sorting
In plain English: Sort a list by picking a pivot, putting smaller elements left and larger right, then recursing.
Partitioning places the pivot in its final sorted position — everything left is smaller, everything right is larger.
Prompt
Sort an array using quicksort with Lomuto partition.
Try to write it from scratch before scrolling down.
Solution
def quicksort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p = partition(a, lo, hi)
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
return a
def partition(a, lo, hi):
pivot = a[hi]
i = lo # i tracks boundary of <= pivot
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return i
# Test: quicksort([10,7,8,9,1,5]) == [1,5,7,8,9,10]