Quick Sort Partition Lomuto and Hoare in DSA Python

Mental Model

Partition splits an array into parts so smaller values go left and bigger go right around a pivot. Lomuto and Hoare are two ways to do this splitting.

Analogy: Imagine sorting books on a shelf by height. Lomuto picks one book as a divider and moves shorter books to the left and taller to the right, scanning from left to right. Hoare uses two hands starting from both ends, swapping books that are out of place until they meet in the middle.

Array: [7, 2, 1, 6, 8, 5, 3, 4]
Pivot chosen (Lomuto): last element 4
Pointers:
Lomuto: i and j scanning from left
Hoare: i from left, j from right

Initial:
Index: 0  1  2  3  4  5  6  7
Value: 7  2  1  6  8  5  3  4
                 ↑           ↑
               i/j         pivot

Dry Run Walkthrough

Input: array: [7, 2, 1, 6, 8, 5, 3, 4]

Goal: Partition the array around pivot 4 using Lomuto and Hoare methods

Step 1: Lomuto: set pivot=4, i=-1, j=0 start scanning

Array: [7, 2, 1, 6, 8, 5, 3, 4]
i=-1, j=0

Why: Initialize i before start to track smaller elements

Step 2: Lomuto: j=0 value 7 > pivot 4, no swap, j++

Array: [7, 2, 1, 6, 8, 5, 3, 4]
i=-1, j=1

Why: 7 is bigger than pivot, so leave it on right side

Step 3: Lomuto: j=1 value 2 < pivot 4, i=0, swap arr[i] and arr[j]

Array: [2, 7, 1, 6, 8, 5, 3, 4]
i=0, j=1

Why: 2 is smaller, move it left by swapping with element at i

Step 4: Lomuto: j=2 value 1 < pivot 4, i=1, swap arr[i] and arr[j]

Array: [2, 1, 7, 6, 8, 5, 3, 4]
i=1, j=2

Why: 1 is smaller, move it left

Step 5: Lomuto: j=3 value 6 > pivot 4, no swap, j++

Array: [2, 1, 7, 6, 8, 5, 3, 4]
i=1, j=3

Why: 6 bigger than pivot, keep right

Step 6: Lomuto: j=4 value 8 > pivot 4, no swap, j++

Array: [2, 1, 7, 6, 8, 5, 3, 4]
i=1, j=4

Why: 8 bigger than pivot, keep right

Step 7: Lomuto: j=5 value 5 > pivot 4, no swap, j++

Array: [2, 1, 7, 6, 8, 5, 3, 4]
i=1, j=5

Why: 5 bigger than pivot, keep right

Step 8: Lomuto: j=6 value 3 < pivot 4, i=2, swap arr[i] and arr[j]

Array: [2, 1, 3, 6, 8, 5, 7, 4]
i=2, j=6

Why: 3 smaller, move left

Step 9: Lomuto: end of loop, swap arr[i+1=3] with pivot at high=7

Array: [2, 1, 3, 4, 8, 5, 7, 6]
final pivot index=3

Why: Place pivot after smaller elements

Step 10: Hoare: set pivot=4 (arr[7]), i=0, j=7

Array: [7, 2, 1, 6, 8, 5, 3, 4]
i=0, j=7

Why: Initialize pointers at bounds

Step 11: i moves right while arr[i]<pivot; j moves left while arr[j]>pivot

Array: [7, 2, 1, 6, 8, 5, 3, 4]
i=0, j=7

Why: Find first i >= pivot and first j <= pivot

Step 12: i=0 < j=7, swap arr[0]↔arr[7]

Array: [4, 2, 1, 6, 8, 5, 3, 7]
i=0, j=7

Why: Swap out-of-place elements

Step 13: i moves right past 2,1; stops at 6; j moves left past 3; stops at 3

Array: [4, 2, 1, 6, 8, 5, 3, 7]
i=3, j=6

Why: Move pointers past elements in place

Step 14: i=3 < j=6, swap arr[3]↔arr[6]

Array: [4, 2, 1, 3, 8, 5, 6, 7]
i=3, j=6

Why: Swap 6 (>pivot) and 3 (<pivot)

Step 15: i moves right stops at 8; j moves left stops at 3; pointers crossed

Array: [4, 2, 1, 3, 8, 5, 6, 7]
i=4, j=3

Why: Continue moving until cross

Step 16: i >= j, return partition index j=3

Array: [4, 2, 1, 3, 8, 5, 6, 7]

Why: Pointers crossed, partition complete

Result:

Lomuto partitioned array: [2, 1, 3, 4, 8, 5, 7, 6]
Pivot index: 3
Hoare partitioned array: [4, 2, 1, 3, 8, 5, 6, 7]
Partition index: 3

Annotated Code

DSA Python

class QuickSortPartition:
    def lomuto_partition(self, arr, low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]  # swap smaller element left
        arr[i + 1], arr[high] = arr[high], arr[i + 1]  # place pivot after smaller
        return i + 1

    def hoare_partition(self, arr, low, high):
        pivot = arr[low]
        i = low - 1
        j = high + 1
        while True:
            i += 1
            while arr[i] < pivot:
                i += 1  # move i right
            j -= 1
            while arr[j] > pivot:
                j -= 1  # move j left
            if i >= j:
                return j
            arr[i], arr[j] = arr[j], arr[i]  # swap out-of-place


if __name__ == '__main__':
    arr_lomuto = [7, 2, 1, 6, 8, 5, 3, 4]
    arr_hoare = arr_lomuto.copy()
    qsp = QuickSortPartition()

    pivot_index_lomuto = qsp.lomuto_partition(arr_lomuto, 0, len(arr_lomuto) - 1)
    print('Lomuto partitioned array:', ' -> '.join(map(str, arr_lomuto)) + ' -> null')
    print('Pivot index:', pivot_index_lomuto)

    pivot_index_hoare = qsp.hoare_partition(arr_hoare, 0, len(arr_hoare) - 1)
    print('Hoare partitioned array:', ' -> '.join(map(str, arr_hoare)) + ' -> null')
    print('Partition index:', pivot_index_hoare)

pivot = arr[high]

select pivot as last element for Lomuto

i = low - 1

initialize i before start to track smaller elements

for j in range(low, high):

scan array from low to high-1

if arr[j] < pivot:

check if current element smaller than pivot

i += 1 arr[i], arr[j] = arr[j], arr[i]

increment i and swap smaller element left

arr[i + 1], arr[high] = arr[high], arr[i + 1]

place pivot after smaller elements

pivot = arr[low]

select pivot as first element for Hoare

i = low - 1 j = high + 1

initialize pointers outside array bounds

while True:

loop until pointers cross

i += 1 while arr[i] < pivot: i += 1

move i right to find element >= pivot

j -= 1 while arr[j] > pivot: j -= 1

move j left to find element <= pivot

if i >= j: return j

stop when pointers cross

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

swap out-of-place elements

Output

Lomuto partitioned array: 2 -> 1 -> 3 -> 4 -> 8 -> 5 -> 7 -> 6 -> null

Pivot index: 3

Hoare partitioned array: 4 -> 2 -> 1 -> 3 -> 8 -> 5 -> 6 -> 7 -> null

Partition index: 3

Complexity Analysis

Time: O(n) because each partition scans the array once with pointer moves

Space: O(1) because partitioning is done in place without extra arrays

vs Alternative: Compared to naive partition that uses extra arrays for smaller and bigger elements, Lomuto and Hoare do partitioning in place saving space and time

Edge Cases

empty array

partition returns immediately without changes

DSA Python

for j in range(low, high):

array with one element

partition returns the single element index without swaps

DSA Python

for j in range(low, high):

all elements equal

Lomuto places pivot at end, Hoare pointers cross quickly, minimal swaps

DSA Python

if arr[j] < pivot:

When to Use This Pattern

When you see a problem asking to sort or rearrange elements around a pivot efficiently, reach for Quick Sort partition patterns like Lomuto or Hoare because they split arrays in place for fast sorting.

Common Mistakes

Mistake: Using Lomuto but forgetting to swap pivot at the end
Fix: Always swap pivot with element at i+1 after scanning to place pivot correctly

Mistake: In Hoare, moving pointers incorrectly causing infinite loop
Fix: Ensure pointers move inside while loops and stop when crossing

Summary

Partitions an array around a pivot so smaller elements go left and bigger go right.

Use when implementing Quick Sort to efficiently split arrays for sorting.

Lomuto scans left to right with one pointer tracking smaller elements; Hoare uses two pointers from both ends swapping out-of-place elements until they meet.

Practice

1. What is the main difference between Lomuto and Hoare partition schemes in Quick Sort?

easy

A. Lomuto sorts the array, Hoare only partitions without sorting

B. Lomuto uses a single pointer to partition, Hoare uses two pointers moving inward

C. Hoare uses recursion, Lomuto does not

D. Lomuto always picks the last element as pivot, Hoare picks the first element

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses one pointer to track the boundary of smaller elements and swaps elements accordingly.

2. Step 2: Understand Hoare partition

   Hoare partition uses two pointers starting from both ends moving inward to swap elements around the pivot.

3. Final Answer:

   Lomuto uses a single pointer to partition, Hoare uses two pointers moving inward -> Option B

4. Quick Check:

   Partition schemes differ by pointer usage = A [OK]

Hint: Remember: Lomuto one pointer, Hoare two pointers [OK]

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking Hoare does not partition
• Assuming Lomuto uses two pointers

2. Which of the following is the correct syntax for Lomuto partition function header in Python?

easy

A. def lomuto_partition(arr):

B. def lomuto_partition(arr, start, end):

C. def lomuto_partition(arr, low, high):

D. def lomuto_partition(low, high, arr):

Solution

1. Step 1: Check parameter order and names

   Lomuto partition typically takes array, low index, and high index as parameters in that order.

2. Step 2: Validate function header syntax

   def lomuto_partition(arr, low, high): matches the common and correct syntax: def lomuto_partition(arr, low, high):

3. Final Answer:

   def lomuto_partition(arr, low, high): -> Option C

4. Quick Check:

   Correct function header = C [OK]

Hint: Remember parameter order: array, low, high [OK]

Common Mistakes:

• Swapping parameter order
• Missing parameters
• Using incorrect parameter names

3. What is the output of the following code using Lomuto partition?

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

arr = [8, 3, 7, 6, 2]
index = lomuto_partition(arr, 0, 4)
print(arr)

medium

A. [2, 3, 6, 7, 8]

B. [3, 2, 7, 6, 8]

C. [8, 3, 7, 6, 2]

D. [2, 3, 7, 6, 8]

Solution

1. Step 1: Identify pivot and initial pointers

   Pivot is arr[4] = 2. i starts at -1.

2. Step 2: Iterate and swap elements <= pivot

   Check elements from index 0 to 3: - arr[0]=8 > 2 no swap - arr[1]=3 > 2 no swap - arr[2]=7 > 2 no swap - arr[3]=6 > 2 no swap No i increment, i stays -1.

3. Step 3: Swap pivot with arr[i+1]

   Swap arr[0] and arr[4]: arr becomes [2, 3, 7, 6, 8]

4. Final Answer:

   [2, 3, 7, 6, 8] -> Option D

5. Quick Check:

   Pivot 2 placed at start, smaller elements left = A [OK]

Hint: Pivot swaps at i+1 after loop ends [OK]

Common Mistakes:

• Swapping pivot too early
• Incrementing i incorrectly
• Confusing pivot index

4. Find the error in this Hoare partition implementation:

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high
    while True:
        while i <= high and arr[i] < pivot:
            i += 1
        while j >= low and arr[j] > pivot:
            j -= 1
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    arr[low], arr[j] = arr[j], arr[low]
    return j

arr = [5, 2, 9, 1, 5, 6]
index = hoare_partition(arr, 0, 5)
print(arr)

medium

A. The swap of pivot with arr[j] is incorrect in Hoare partition

B. i should start at low, not low + 1

C. Pivot should be arr[high], not arr[low]

D. The inner while loops should use <= and >= incorrectly

Solution

1. Step 1: Review Hoare partition pivot swap

   Hoare partition does NOT swap pivot with arr[j] at the end; it returns j as partition index.

2. Step 2: Check code's final swap

   This code swaps arr[low] and arr[j], which is incorrect and can misplace pivot.

3. Final Answer:

   The swap of pivot with arr[j] is incorrect in Hoare partition -> Option A

4. Quick Check:

   Hoare returns index without swapping pivot at end = B [OK]

Hint: Hoare returns index, no pivot swap at end [OK]

Common Mistakes:

• Swapping pivot at end in Hoare
• Starting pointers incorrectly
• Misusing loop conditions

5. Given the array [10, 80, 30, 90, 40, 50, 70], what is the array state after applying Hoare partition with pivot as first element?

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

arr = [10, 80, 30, 90, 40, 50, 70]
index = hoare_partition(arr, 0, 6)
print(arr)

hard

A. [10, 80, 30, 90, 40, 50, 70]

B. [10, 70, 30, 90, 40, 50, 80]

C. [10, 50, 30, 40, 70, 80, 90]

D. [10, 30, 40, 50, 70, 80, 90]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = 10, i = -1, j = 7 initially.

2. Step 2: Move pointers and swap

   Loop 1: - i increments to 0, arr[i]=10 not < pivot, stop - j decrements to 6, arr[6]=70 > 10, j=5 arr[5]=50 > 10, j=4 arr[4]=40 > 10, j=3 arr[3]=90 > 10, j=2 arr[2]=30 > 10, j=1 arr[1]=80 > 10, j=0 arr[0]=10 not > 10, stop - i=0, j=0, i >= j so return j=0 No swaps done, array unchanged.

3. Step 3: Check if any swaps occurred

   Since i >= j immediately, no swaps happened, array remains same.

4. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option A

5. Quick Check:

   Pivot 10 smallest, no swaps = D [OK]

Hint: Hoare stops when pointers cross, may do no swaps [OK]

Common Mistakes:

• Assuming pivot moves at end
• Misunderstanding pointer increments
• Expecting sorted array after partition