DSA · Chapter 33 of 40
Quick Sort
Quick sort picks a pivot, partitions the array so smaller elements go left and larger go right, then sorts each side recursively. Average time is O(n log n) with O(log n) stack space and no extra array.
The worst case is O(n^2) when the pivot is always the smallest or largest element, which is why random or median-of-three pivots are used.
Partitioning
Lomuto and Hoare are the two common partition schemes; both rearrange the array in place around the pivot.
Quickselect
The same partition idea finds the k-th smallest element in average O(n) without sorting everything.
Example 1 (python)
def quick_sort(a):
if len(a) <= 1:
return a
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quick_sort(left) + mid + quick_sort(right)
print(quick_sort([5, 3, 8, 1]))Output
[1, 3, 5, 8]A readable (though not in-place) version of quick sort.
Example 2 (python)
def quickselect(a, k):
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
mid = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
if k < len(left):
return quickselect(left, k)
if k < len(left) + len(mid):
return pivot
return quickselect(right, k - len(left) - len(mid))
print(quickselect([7, 2, 9, 4], 1))Output
4Quickselect finds the k-th smallest in average O(n).
Key points
- Average O(n log n), worst case O(n^2).
- It sorts in place with O(log n) stack space.
- Random or median-of-three pivots avoid the worst case.
- Quickselect finds the k-th element in average O(n).
💡 Note: Quick sort is usually faster in practice than merge sort due to cache locality.