Partitioning
- Algorithms course
- Intermediate
- Lesson 6/80
- 4 min
Put smaller-than-pivot left, larger right.
Partitioning
Partitioning moves elements smaller than the pivot to the left, larger to the right. Done in one pass, O(n).
The classic Lomuto scheme: an i pointer marks the boundary of smaller elements. Each element is compared to the pivot; if smaller, i advances and we swap.
Finally the pivot is placed at i+1; the left side is smaller, the right side is larger. The pivot is now in its final place.
Lomuto scheme
Lomuto's scheme is easy to follow but does more swaps than Hoare's. Start with i = lo - 1; on each smaller element do i += 1 and swap.
After the pass, swap the pivot with i+1; the return value is i+1 (the pivot's new position).
This position defines the boundary for left and right recursive subarrays.
Practice Partition — Lomuto
Write partition(arr, lo, hi). arr[hi] is the pivot. Move smaller to the left, place the pivot, return its index. Print 3 with arr=[4,2,7,1,5]; print(partition(arr,0,4)).
Starter code
def partition(arr, lo, hi):
# Lomuto partitionSample solution
def partition(arr, lo, hi):
# Lomuto partition
pivot = arr[hi]
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 = [4, 2, 7, 1, 5]
print(partition(arr, 0, 4))Expected output
3
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Swap
arr[i], arr[j] = arr[j], ____arr[i], arr[j] = arr[j], arr[i]Explanation: arr[i] is right.
2 Partitioning: match the terms
| Term | Meaning |
|---|---|
i pointer |
Smaller boundary |
Pivot |
Last element |
Swap |
Exchange |
Return |
Pivot position |
3 How much work does the partition step do?
- O(1)
- O(log n)
- O(n) Correct answer
- O(n^2)
Explanation: O(n)