Course contentsShow
← Computer Science
Lesson 765 of 2,87218. Sorting AlgorithmsFree lesson

Lomuto Partition Scheme

Implement the simple Lomuto partitioning algorithm that uses a single index to divide the array.

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

  1. Choose the last element as the pivot
  2. Keep an index i that marks the boundary of smaller elements (starts at -1 or one before the first position)
  3. Loop through each element with index j from start to end-1:
    • If array[j] < pivot, increment i and swap array[i] with array[j]
  4. After the loop, swap the pivot (at the end) with array[i+1]
  5. Return i+1 as 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.