Quick Sort Partition Lomuto and Hoare in DSA Go

Mental Model

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

Analogy: Imagine sorting books on a shelf by height: Lomuto picks one book as a divider and moves shorter books left and taller right, while Hoare uses two hands from both ends to swap books until they meet.

Array: [5, 3, 8, 4, 2]
Pivot: 2 (Lomuto picks last element)
Indexes: i and j move to rearrange

Initial:
[5, 3, 8, 4, 2]
 i= -1, j=0

After partition:
[2, 3, 8, 4, 5]
Pivot at index 0

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2], partition using Lomuto and Hoare

Goal: Show how Lomuto and Hoare partition rearrange the array around the pivot

Step 1: Lomuto: set pivot as last element (2), i = -1

[5, 3, 8, 4, 2]
i = -1, j = 0

Why: Pivot chosen to compare others against; i tracks smaller elements

Step 2: Lomuto: j=0 (5 > 2), no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 1

Why: 5 is bigger than pivot, so no move

Step 3: Lomuto: j=1 (3 > 2), no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 2

Why: 3 is bigger than pivot, no move

Step 4: Lomuto: j=2 (8 > 2), no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 3

Why: 8 is bigger than pivot, no move

Step 5: Lomuto: j=3 (4 > 2), no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 4

Why: 4 is bigger than pivot, no move

Step 6: Lomuto: swap pivot (2) with element at i+1 (5)

[2, 3, 8, 4, 5]
i = 0

Why: Place pivot in correct position so left are smaller

Step 7: Hoare: set pivot as first element (5), i=0, j=5

[5, 3, 8, 4, 2]
i=0, j=5

Why: Pivot chosen at start; i and j move inward

Step 8: Hoare: move j left while arr[j] > pivot (j moves from 5 to 4, arr[4]=2 <= 5 stops at j=4)

[5, 3, 8, 4, 2]
i=0, j=4

Why: Find element smaller than pivot from right

Step 9: Hoare: move i right while arr[i] < pivot (3 < 5 at i=1, 8 > 5 stops at i=2)

[5, 3, 8, 4, 2]
i=2, j=4

Why: Find element bigger than pivot from left

Step 10: Hoare: swap arr[i] (8) and arr[j] (2)

[5, 3, 2, 4, 8]
i=2, j=4

Why: Swap out-of-place elements to correct sides

Step 11: Hoare: move j left (j=3, arr[3]=4 < 5 stops), move i right (i=3, arr[3]=4 < 5 moves to i=3)

[5, 3, 2, 4, 8]
i=3, j=3

Why: Continue scanning inward

Step 12: Hoare: i >= j (3 >= 3), partition ends, return j=3

[5, 3, 2, 4, 8]

Why: Pointers crossed, partition done

Result:

Lomuto partition result: [2, 3, 8, 4, 5], pivot index 0
Hoare partition result: [5, 3, 2, 4, 8], partition index 3

Annotated Code

DSA Go

package main

import "fmt"

// Lomuto partition scheme
func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high] // pivot is last element
    i := low - 1       // i tracks smaller element index
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i] // swap smaller element to front
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1] // place pivot after smaller elements
    return i + 1
}

// Hoare partition scheme
func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low] // pivot is first element
    i := low - 1
    j := high + 1
    for {
        for {
            j--
            if arr[j] <= pivot {
                break
            }
        }
        for {
            i++
            if arr[i] >= pivot {
                break
            }
        }
        if i < j {
            arr[i], arr[j] = arr[j], arr[i] // swap out-of-place elements
        } else {
            return j
        }
    }
}

func main() {
    arr1 := []int{5, 3, 8, 4, 2}
    p1 := lomutoPartition(arr1, 0, len(arr1)-1)
    fmt.Printf("Lomuto partition result: %v, pivot index %d\n", arr1, p1)

    arr2 := []int{5, 3, 8, 4, 2}
    p2 := hoarePartition(arr2, 0, len(arr2)-1)
    fmt.Printf("Hoare partition result: %v, partition index %d\n", arr2, p2)
}

pivot := arr[high] // pivot is last element

select pivot for Lomuto partition

i := low - 1 // i tracks smaller element index

initialize i before low

if arr[j] <= pivot { i++; swap arr[i], arr[j] }

move smaller or equal elements left

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

place pivot after smaller elements

pivot := arr[low] // pivot is first element

select pivot for Hoare partition

j-- until arr[j] <= pivot

move j left to find smaller or equal element

i++ until arr[i] >= pivot

move i right to find bigger or equal element

if i < j { swap arr[i], arr[j] } else { return j }

swap out-of-place elements or end partition

Output

Lomuto partition result: [2 3 8 4 5], pivot index 0

Hoare partition result: [5 3 2 4 8], partition index 3

Complexity Analysis

Time: O(n) because each partition scans the array once with pointers moving inward

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

vs Alternative: Compared to naive partition that might use extra arrays, these in-place methods save space and are faster

Edge Cases

array with all equal elements

Lomuto places pivot at end; Hoare partitions but may return low index; both handle gracefully

DSA Go

if arr[j] <= pivot { i++; swap arr[i], arr[j] }

array with single element

partition returns the single index without swaps

DSA Go

for j := low; j < high; j++ { ... }

empty array

partition functions are not called or return immediately

DSA Go

main driver controls input size before calling partition

When to Use This Pattern

When you see a problem asking to sort or rearrange around a pivot quickly, think of Lomuto or Hoare partition schemes as the core step in quicksort.

Common Mistakes

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

Mistake: In Hoare, moving pointers incorrectly causing infinite loops
Fix: Ensure inner loops move pointers until correct condition before swapping or returning

Summary

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

Use when implementing quicksort to efficiently divide the array for recursive sorting.

The key insight is how pointers move and swap elements to place the pivot correctly without extra space.

Practice

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

easy

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

B. Lomuto sorts the array in descending order, Hoare sorts in ascending order

C. Lomuto requires extra memory, Hoare works in-place

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

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 A

4. Quick Check:

   Partition pointers = single vs two [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking Lomuto uses two pointers
• Assuming Hoare needs extra memory

2. Which of the following is the correct Lomuto partition function header in Go?

easy

A. func lomutoPartition(arr []int, low int, high int) int

B. func lomutoPartition(arr []int) int

C. func lomutoPartition(arr []int, pivot int) int

D. func lomutoPartition(arr []int, start int, end int) bool

Solution

1. Step 1: Check parameters needed for Lomuto

   Lomuto partition requires the array and indices low and high to define the subarray.

2. Step 2: Check return type

   It returns an integer index of the pivot after partitioning.

3. Final Answer:

   func lomutoPartition(arr []int, low int, high int) int -> Option A

4. Quick Check:

   Function signature = arr, low, high, returns int [OK]

Hint: Lomuto needs array and low, high indices, returns pivot index [OK]

Common Mistakes:

• Omitting low and high parameters
• Returning bool instead of int
• Passing pivot as parameter explicitly

3. What is the output array after applying Lomuto partition on [8, 3, 7, 6, 2] with pivot as last element?

medium

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

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

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

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

Solution

1. Step 1: Identify pivot and initialize pointers

   Pivot is last element 2. Initialize i = low - 1 = -1.

2. Step 2: Iterate and swap elements smaller than pivot

   Check elements: 8 > 2 no swap, 3 > 2 no swap, 7 > 2 no swap, 6 > 2 no swap. i stays -1. Finally swap pivot with arr[i+1] = arr[0].

3. Final Answer:

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

4. Quick Check:

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

Hint: Pivot last element, swap smaller left, pivot next [OK]

Common Mistakes:

• Swapping elements incorrectly
• Not updating i pointer properly
• Confusing pivot position after partition

4. Given this Hoare partition code snippet in Go, what is the bug?

func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low]
    i := low - 1
    j := high + 1
    for {
        for arr[i] < pivot {
            i++
        }
        for arr[j] > pivot {
            j--
        }
        if i >= j {
            return j
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
}

medium

A. The inner loops should use <= and >= instead of < and >

B. Pivot should be arr[high] instead of arr[low]

C. i and j initialization should be i = low, j = high

D. The swap should happen after checking i > j

Solution

1. Step 1: Check pointer initialization

   In Hoare partition, i starts at low and j at high, not outside the array bounds.

2. Step 2: Understand loop conditions

   Starting i at low - 1 and j at high + 1 causes index out of range errors during arr[i] and arr[j] access.

3. Final Answer:

   i and j initialization should be i = low, j = high -> Option C

4. Quick Check:

   Pointer start = low, high [OK]

Hint: Hoare pointers start at low and high, not outside [OK]

Common Mistakes:

• Initializing pointers outside array bounds
• Using wrong pivot element
• Swapping before pointer check

5. You want to sort an array with many duplicate elements efficiently. Which partition scheme is better and why?

hard

A. Lomuto, because it handles duplicates by placing them all on one side

B. Hoare, because it partitions elements more evenly and reduces swaps with duplicates

C. Lomuto, because it uses two pointers to handle duplicates quickly

D. Hoare, because it always picks the last element as pivot

Solution

1. Step 1: Consider duplicate handling in Lomuto

   Lomuto tends to put duplicates on one side, causing unbalanced partitions and more recursive calls.

2. Step 2: Consider duplicate handling in Hoare

   Hoare's two-pointer approach partitions more evenly, reducing swaps and improving performance with duplicates.

3. Final Answer:

   Hoare, because it partitions elements more evenly and reduces swaps with duplicates -> Option B

4. Quick Check:

   Duplicates handled better by Hoare [OK]

Hint: Hoare partitions evenly, better for duplicates [OK]

Common Mistakes:

• Assuming Lomuto is better for duplicates
• Confusing pivot choice with partition efficiency
• Ignoring swap count impact