Partitioning

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.

Exercise 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)).

Show example 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))

Test yourself

Swap

arr[i], arr[j] = arr[j], ____

Show answer

arr[i], arr[j] = arr[j], arr[i]

Partitioning: match the terms

i pointer

Smaller boundary
Pivot

Last element
Swap

Exchange
Return

Pivot position
How much work does the partition step do?
- O(1)
- O(log n)
- O(n)
- O(n^2)
Show answer

O(n) — O(n)

Next lesson: Recursive quick sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies