Quick Sort Animation
–
Waiting for input...
Ready
Color: Pivot • i (boundary) • j (scanner) • Compare • Swap
Quick Sort
Step through quick sort's partitioning - see how pivots divide and conquer the array.
Time O(n log n) · Space O(log n) · Unstable
Implementation
def quick_sort_lomuto_random_pivot(arr):
def partition(low, high):
from random import randint
# unlike in range(), here upperbound is included
pivot_pos = randint(low, high)
arr[pivot_pos], arr[high] = arr[high], arr[pivot_pos]
pivot = arr[high]
i = low - 1 # `i` tracks last el < pivot
for j in range(low, high): # `j` iterates array, compares each el to pivot
if arr[j] < pivot:
i += 1 # when arr[j] < pivot, it will be brought to the back, and `i` will track its position
arr[i], arr[j] = arr[j], arr[i]
# arr[i] is now the last el < pivot => `i+1` will be the new place of the pivot
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def sorting(low, high):
if low >= high:
return
pivot_pos = partition(low, high)
sorting(low, pivot_pos - 1)
sorting(pivot_pos + 1, high)
low = 0
high = len(arr) - 1
sorting(low, high)
return arr
About Quick Sort
How Quick Sort Works
Quick sort selects a pivot element and partitions the array so that elements less than the pivot come before it and elements greater come after. It then recursively sorts the partitions. In practice, it is one of the fastest general-purpose sorting algorithms.
Choose a pivot element, then rearrange the array so all elements smaller than the pivot are on its left, and all larger elements are on its right. Recursively apply the same process to the left and right partitions.
Complexity
- Time
- O(n log n)
- Space
- O(log n)
- Stability
- unstable
When to Use Quick Sort
- General-purpose sorting with excellent average performance
- In-memory sorting where cache performance matters
- Large datasets where average-case O(n log n) is acceptable