DSA Quick Sort
Quick sort selects a pivot element, partitions the rest of the list around it, and recursively sorts the two resulting partitions.
The Partition Step
Partitioning is the heart of quick sort. Given a pivot value, the partition step rearranges the array so that every element smaller than the pivot ends up to its left, and every element greater ends up to its right. The pivot then sits at its final sorted position, and the two partitions on either side can be sorted independently and recursively.
- Choose a pivot element from the sub-array.
- Rearrange elements so smaller values move left of the pivot and larger values move right.
- Place the pivot at the boundary between the two groups.
- Recursively apply the same process to the left and right partitions.
- Stop recursing once a partition has zero or one element.
Example
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_index = partition(arr, low, high)
quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)
return arr
print(quick_sort([10, 7, 8, 9, 1, 5]))Choosing a Pivot
The choice of pivot determines how balanced the partitions are. Always picking the first or last element works fine on random data but performs badly on already-sorted or reverse-sorted input, where every partition splits off just one element at a time. Choosing a random element, or the median of the first, middle, and last elements, avoids these adversarial cases in practice.
Example
import random
def partition_random(arr, low, high):
random_index = random.randint(low, high)
arr[random_index], arr[high] = arr[high], arr[random_index]
return partition(arr, low, high)
def quick_sort_random(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low < high:
pivot_index = partition_random(arr, low, high)
quick_sort_random(arr, low, pivot_index - 1)
quick_sort_random(arr, pivot_index + 1, high)
return arr
print(quick_sort_random([33, 10, 55, 71, 29, 3]))Complexity Analysis
Example
def quick_sort_functional(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort_functional(left) + middle + quick_sort_functional(right)
print(quick_sort_functional([8, 4, 7, 3, 10, 2]))Exercise: DSA Quick Sort
What is the core strategy quick sort uses to sort a list?
