Quick Sort and Pivot Selection
Build quick sort with Lomuto and Hoare partition schemes, discuss worst-case O(n²) and how randomised pivot selection mitigates it.
Quick Sort: In-Place Divide and Conquer
Quick sort is the most widely used sorting algorithm in practice. Unlike merge sort, it sorts in-place without allocating extra arrays. The core idea: choose a pivot element, partition the array so all elements less than the pivot come before it and all greater elements after it, then recursively sort each partition. The partition step takes O(n) time, and with a good pivot, the recursion depth is O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Lomuto Partition Scheme
The Lomuto partition uses the last element as pivot. A slow pointer i tracks the boundary of the 'less than pivot' region; a fast pointer j scans forward. When arr[j] <= pivot, increment i and swap arr[i] with arr[j], extending the small-element region. After the scan, place the pivot at i+1 by swapping with arr[hi]. Simple to implement but performs 3× more swaps than Hoare's scheme.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)All lessons in this course
- Bubble Sort and Insertion Sort
- Merge Sort: Divide, Sort, Merge
- Quick Sort and Pivot Selection
- Non-Comparison Sorts and Python's sort()