How it works
Choose a pivot (last element here). Use two pointers: scan left to right. If element ≤ pivot, swap it to the "less than" partition. After scanning, swap pivot to its final position. Recurse on both sides.
Lomuto Partition
pivot = arr[high]
i = low - 1 // boundary of "≤ pivot"
for j = low to high-1:
if arr[j] <= pivot:
i++, swap(arr[i], arr[j])
swap(arr[i+1], arr[high]) // place pivot
i = low - 1 // boundary of "≤ pivot"
for j = low to high-1:
if arr[j] <= pivot:
i++, swap(arr[i], arr[j])
swap(arr[i+1], arr[high]) // place pivot
Interactive Visualization
Pivot Comparing Swapping Final Position
Array
Bar Chart
Step 0 of 0
Pivot
—
Comparisons
0
Swaps
0
Partitions
0
Ready. Press Play or Next to start.
✓ Sorted
Speed
C++ — Quick Sort (Lomuto)
int partition(vector<int>& arr, int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; swap(arr[i], arr[j]); } } swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(vector<int>& arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }
Complexity
Time (Average)
O(N log N)
Balanced partitions on average.
Time (Worst)
O(N²)
Already sorted + bad pivot (rare with randomization).
Space
O(log N)
Stack space for recursion.
Stable?
No
Partition swaps break relative order.