Lomuto Partition Scheme
You'll learn how to implement the simpler of the two main partitioning approaches used in Quicksort, which uses a single index to rearrange elements around a pivot.
What Is the Lomuto Partition Scheme?
The Lomuto partition scheme is a straightforward way to perform the partition operation in Quicksort. It typically chooses the last element as the pivot and uses one index to track where smaller elements should go. As you scan through the array, whenever you find an element smaller than the pivot, you swap it into the "small elements" section.
How It Works
Imagine organizing books on a shelf where you've decided the last book is your reference point. You walk from left to right. Every time you find a book that should come before your reference book (alphabetically, say), you move it to the front section. At the end, you place the reference book right between the "earlier" and "later" sections.
The Algorithm Steps
- Choose the last element as the pivot
- Keep an index
ithat marks the boundary of smaller elements (starts at -1 or one before the first position) - Loop through each element with index
jfrom start to end-1:- If
array[j] < pivot, incrementiand swaparray[i]witharray[j]
- If
- After the loop, swap the pivot (at the end) with
array[i+1] - Return
i+1as the pivot's final position
All elements before index i+1 are smaller than the pivot; all after are greater or equal.
Key Takeaway: The Lomuto partition scheme uses a single boundary index to sweep through the array once, swapping smaller elements to the left section, making it simple to understand and implement.