Partition an Array With the Lomuto Scheme

One index scans, the other marks where the next smaller item goes, and a last swap places the pivot.

The Lomuto scheme partitions a range around its last item using two indices and a series of swaps, and it is the partition most courses teach first because each step is a single comparison. This card walks through its method, a prediction to make, and a trace of one partition with every swap.

The method has four moves:

Take the last item of the range as the pivot.
Set i to the first index of the range. Everything before i will be smaller than the pivot.
Move j from the first index up to the one before the pivot. Whenever the item at j is smaller than the pivot, swap it with the item at i and move i on by one. Otherwise leave it where it is.
Swap the pivot with the item at i. The pivot now sits at index i, with every smaller item before it and every other item after it.

Partition 7 2 8 1 5 3 6 around its last item, 6. Before the trace, predict the array afterwards and the index where 6 ends up.

Show the prediction

The array is 2 1 5 3 6 7 8, with 6 at index 4. Four items, 2, 1, 5 and 3, are smaller than 6, so they fill indices 0 to 3 and 6 goes straight after them. Moving them took four swaps, and placing the pivot one more.

In the trace, i and j sit where they were at the moment of each swap, and pivot marks the pivot's index. An item that is not smaller than 6 is passed over without a frame of its own, which is why 7 and 8 stay put until a smaller item is swapped into their slot.

Lomuto partition of 7 2 8 1 5 3 6 around its last item

Input7 2 8 1 5 3 6

Start
1. 7ij
2. 2
3. 8
4. 1
5. 5
6. 3
7. 6pivot
The pivot is 6, the last item. i marks the next slot for an item smaller than the pivot, and j scans every item before the pivot.
Swap 2
1. 2i
2. 7j
3. 8
4. 1
5. 5
6. 3
7. 6pivot
7 is not smaller than 6, so j passed it. 2 is smaller, so it swaps into slot i, index 0, and i moves on to 1.
Swap 1
1. 2
2. 1i
3. 8
4. 7j
5. 5
6. 3
7. 6pivot
8 is not smaller, so j passed it. 1 is smaller, so it swaps with 7 into slot 1.
Swap 5
1. 2
2. 1
3. 5i
4. 7
5. 8j
6. 3
7. 6pivot
5 is smaller, so it swaps with 8 into slot 2.
Swap 3
1. 2
2. 1
3. 5
4. 3i
5. 8
6. 7j
7. 6pivot
3 is smaller, so it swaps with 7 into slot 3. j has reached the pivot.
Place pivot
1. 2
2. 1
3. 5
4. 3
5. 6pivot
6. 7
7. 8
The last swap moves 6 into slot i, index 4. Everything to its left is smaller and everything to its right is larger.

Result2 1 5 3 6 7 8, pivot at index 4

The run's last frame matches the prediction. The two sides are not sorted, 2 1 5 3 on the left and 7 8 on the right: a partition only separates the smaller items from the rest, and the recursive calls sort each side later.

A swap moves an item a long way in one step, over items it is never compared with, and that is why quicksort is not stable. Records with keys 3, 1, 3 and 2, the two 3s tagged a and b in input order, came out of one Lomuto partition around 2 as 1 2 3b 3a in a run: the swap that placed the pivot carried 3a past 3b.

The partition compares each item before the pivot with the pivot exactly once, n − 1 comparisons for a range of n items, and makes at most n swaps, so it takes O(n) time and O(1) extra memory. The cost of the whole sort therefore comes down to how many levels of partitions there are, and that depends on where each pivot lands.

← → move through sections and cards