Sitting with: Lomuto’s Partitioning Scheme

I snagged this pseudocode from Wikipedia and I am planning on going through it step by step to understand what is going on. I recommend having this snippet handy for reference. Here is my breakdown.

algorithm partition(A, lo, hi) is
    pivot := A[hi]
    i := lo
    for j := lo to hi do
        (breakpoint1)
        if A[j] < pivot then
            swap A[i] with A[j]
            (breakpoint2)
            i := i + 1
            (breakpoint3)
    swap A[i] with A[hi]
    return i

The Idea

The Lomuto partitioning scheme is used to partition an array into 2 parts, smaller and bigger than the last element of the same array, called the pivot.

[4,3,31,1,2,25,10,11] => [4,3,1,2,10,11,31,25]

There are two indexes in the algorithm but the star of the play in Lomuto’s partitioning scheme is the index i. i represents the first element that is bigger than the pivot, which in an already partitioned array should be the start of the second half.

The Use Case

If one repeats this partitioning on both left and right subarrays recursively, one end up with a sorted array. This sorting algorithm is called Quicksort. In practice, there is a more optimal partitioning scheme for Quicksort, but this will do for most small use cases. Both partitioning schemes may also be used in Quickselect which is a pretty cool way find K largest or smallest values in an array.

Step by Step

algorithm partition(A, lo, hi) is
    pivot := A[hi]

The pivot is the last element. In the example above, 11.

    i := lo
    for j := lo to hi do

Choose two indexes, i and j. They both start at the beginning of the array. Run j through the array.

         (breakpoint1)
         if A[j] < pivot then
            swap A[i] with A[j]
            (breakpoint2)
            i := i + 1
            (breakpoint3)

This is where the major work happens. This says, if the value at index j is less than the pivot, then swap the element at i with the element at j; then increment i. This makes no sense at first. But it will in a second.

Here is the example array again, we will pause and look at the array every time right before the if block is entered, at breakpoint1; breakpoint2 is only used sometimes.

(breakpoint1)
# Array without indexes(ArNoIdx): [4      ,3,31,1,2,25,10,11]
# Array with indexes(ArWIdx):     [4(i)(j),3,31,1,2,25,10,11]


When the algorithm starts, both i and j are at the first element. The first element, 4, is less than pivot, 11. Thus we enter the if block. We immediately swap the element at i with that at j. Since right now, they are both at the same element. This practically has no effect. We increment i to the next element, 3. Then j moves to the next element, also 3.

(breakpoint1)
# ArNoIdx: [4,3      ,31,1,2,25,10,11]
# ArWIdx:  [4,3(i)(j),31,1,2,25,10,11]

Again, we enter the if block. The swap does nothing and i is incremented by 1, to index 2 with a value of 31. On the next loop, j is incremented to index 2 as well:

(breakpoint1)
# ArNoIdx: [4,3,31      ,1,2,25,10,11]
# ArWIdx:  [4,3,31(i)(j),1,2,25,10,11]


Because 31 is not smaller than the pivot, the if block will not be entered, and the element at index i will not be swapped with the element at index j; nor will index i get incremented.
At this point i is at 31, the first element found to be bigger than the pivot, 11, but j will move onto the next element at index 3 with a value of 1, which is smaller than the pivot.

(breakpoint1)
# ArNoIdx: [4,3,31   ,1   ,2,25,10,11]
# ArWIdx:  [4,3,31(i),1(j),2,25,10,11]

The if block is entered again. i and j are swapped. So now, i is still at its previous index of 2, but it is pointing to a new element, 1, while j is now pointing to 31. Here is a first look at the array at breakpoint2:

(breakpoint2)
# ArNoIdx: [4,3,1   ,31   ,2,25,10,11]
# ArWIdx:  [4,3,1(i),31(j),2,25,10,11]

We then increment i, which will point to 31, where j is, both at index 3:

(breakpoint3)
# ArNoIdx: [4,3,1,31      ,2,25,10,11]
# ArWIdx:  [4,3,1,31(i)(j),2,25,10,11]

In the next iteration, j is at index 4, the value is 2.

(breakpoint1)
# ArNoIdx: [4,3,1,31   ,2   ,25,10,11]
# ArWIdx:  [4,3,1,31(i),2(j),25,10,11]

The if block is entered. i and j are swapped:

(breakpoint2)
# ArNoIdx: [4,3,1,2   ,31   ,25,10,11]
# ArWIdx:  [4,3,1,2(i),31(j),25,10,11]

i moves forward to index 5, 31 again, where j currently is.

(breakpoint3)
# ArNoIdx: [4,3,1,2,31      ,25,10,11]
# ArWIdx:  [4,3,1,2,31(i)(j),25,10,11]

Next iteration, j moves to index 5, the element is 25.

(breakpoint1)
# ArNoIdx: [4,3,1,2,31   ,25   ,10,11]
# ArWIdx:  [4,3,1,2,31(i),25(j),10,11]

25 is bigger than the pivot, so the if block is not entered. i is still at index 4, 31.

For the last iteration, j moves to index 6 with value of 10.

(breakpoint1)
# ArNoIdx: [4,3,1,2,31   ,25,10   ,11]
# ArWIdx:  [4,3,1,2,31(i),25,10(j),11]

10 is less than 11, so the if block is entered, i and j elements are swapped, now i‘s element is 10, while j‘s element is 31.

(breakpoint2)
# ArNoIdx: [4,3,1,2,10   ,25,31   ,11]
# ArWIdx:  [4,3,1,2,10(i),25,31(j),11]

i moves forward to index 5 then, 25.

(breakpoint3)
# ArNoIdx: [4,3,1,2,10,25   ,31   ,11]
# ArWIdx:  [4,3,1,2,10,25(i),31(j),11]

Notice how everything to the left of i(element with value 25) is still smaller than the pivot.

Here, the for loop ends.

    swap A[i] with A[hi]
    return i

This is the last action, we swap the i element, which is still pointing to an element bigger than the pivot, with the pivot element, which is the last element of the array:

[4,3,31,1,2,25,10,11] => [4,3,1,2,10,11,31,25]

This works because i always keeps track of where the second half of the array starts, meaning everything before, has to be smaller than the pivot, while the value at i itself and everything after, except the pivot, must be bigger than the pivot. Then in the end, all that needs to happen to to swap an element bigger than the pivot with the pivot.

We return the index i which is the pivot index in the end.

This is how Lomuto’s partitioning scheme works.

Implementation

Here is a Python implementation:

def lomuto(array):
    lo = 0
    hi = len(array)

    i = 0
    j = 0 
    pivot = array[-1]

    for j in range(lo, hi):
        if array[j] < pivot:
            array[i], array[j] = array[j], array[i]
            i += 1
    
    array[i], array[j] = array[j], array[i]

    return i

One thought on “Sitting with: Lomuto’s Partitioning Scheme

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: