Quick Sort Partition Lomuto and Hoare in DSA Rust

Mental Model

Partition splits an array into parts so smaller values go left and bigger go right around a pivot. Lomuto uses one pointer to separate smaller values, Hoare uses two pointers moving inward.

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

Array: [5, 3, 8, 4, 2]
Pivot: 2 (Lomuto picks last element)
Pointers:
Lomuto: i separates smaller values, j scans
Hoare: i starts left, j starts right

Initial:
[5, 3, 8, 4, 2]
 i ↑        j ↑
Pivot=2

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Partition the array using Lomuto and Hoare methods to rearrange elements around the pivot

Step 1: Lomuto: set pivot=2 (last element), i=-1, j=0 scans

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

Why: Initialize pointers to start partitioning

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

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

Why: 5 is bigger than pivot, keep i to separate smaller values

Step 3: Lomuto: j=1 value=3 > pivot, no swap, i stays -1

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

Why: 3 is bigger than pivot, no change

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

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

Why: 8 is bigger than pivot, no change

Step 5: Lomuto: j=3 value=4 > pivot, no swap, i stays -1

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

Why: 4 is bigger than pivot, no change

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

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

Why: Place pivot in correct position separating smaller and bigger

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

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

Why: Initialize pointers for Hoare partition

Step 8: Hoare: move j left until element <= pivot; j=4 value=2 <=5 stop

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

Why: Find element on right smaller than pivot to swap

Step 9: Hoare: move i right until element >= pivot; i=0 value=5 >=5 stop

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

Why: Find element on left bigger than pivot to swap

Step 10: Hoare: swap elements at i=0 and j=4 (5 and 2)

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

Why: Swap out-of-place elements

Step 11: Hoare: increment i=1, decrement j=3

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

Why: Move pointers inward to continue partition

Step 12: Hoare: move j left until element <= pivot; j=3 value=4 <=5 stop

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

Why: Find next element on right smaller than pivot

Step 13: Hoare: move i right until element >= pivot; i=2 value=8 >=5 stop

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

Why: Find next element on left bigger than pivot

Step 14: Hoare: swap elements at i=2 and j=3 (8 and 4)

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

Why: Swap out-of-place elements

Step 15: Hoare: increment i=3, decrement j=2; now i > j stop

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

Why: Pointers crossed, partition done

Result:

Lomuto partitioned array: [2, 3, 8, 4, 5]
Hoare partitioned array: [2, 3, 4, 8, 5]

Annotated Code

DSA Rust

fn lomuto_partition(arr: &mut [i32]) -> usize {
    let pivot = arr[arr.len() - 1];
    let mut i = -1isize;
    for j in 0..arr.len() - 1 {
        if arr[j] <= pivot {
            i += 1;
            arr.swap(i as usize, j);
        }
    }
    arr.swap((i + 1) as usize, arr.len() - 1);
    (i + 1) as usize
}

fn hoare_partition(arr: &mut [i32]) -> usize {
    let pivot = arr[0];
    let mut i = 0isize;
    let mut j = (arr.len() - 1) as isize;
    loop {
        while arr[j as usize] > pivot {
            j -= 1;
        }
        while arr[i as usize] < pivot {
            i += 1;
        }
        if i >= j {
            return j as usize;
        }
        arr.swap(i as usize, j as usize);
        i += 1;
        j -= 1;
    }
}

fn main() {
    let mut arr_lomuto = vec![5, 3, 8, 4, 2];
    let p_lomuto = lomuto_partition(&mut arr_lomuto);
    println!("Lomuto partition index: {}", p_lomuto);
    println!("Array after Lomuto partition: {:?}", arr_lomuto);

    let mut arr_hoare = vec![5, 3, 8, 4, 2];
    let p_hoare = hoare_partition(&mut arr_hoare);
    println!("Hoare partition index: {}", p_hoare);
    println!("Array after Hoare partition: {:?}", arr_hoare);
}

let pivot = arr[arr.len() - 1];

select pivot as last element for Lomuto

for j in 0..arr.len() - 1 { if arr[j] <= pivot { i += 1; arr.swap(i as usize, j); } }

scan array, move smaller or equal elements left

arr.swap((i + 1) as usize, arr.len() - 1);

place pivot after smaller elements

let pivot = arr[0];

select pivot as first element for Hoare

while arr[j as usize] > pivot { j -= 1; }

move j left to find element <= pivot

while arr[i as usize] < pivot { i += 1; }

move i right to find element >= pivot

if i >= j { return j as usize; }

stop when pointers cross

arr.swap(i as usize, j as usize); i += 1; j -= 1;

swap out-of-place elements and move pointers

Output

Lomuto partition index: 0

Array after Lomuto partition: [2, 3, 8, 4, 5]

Hoare partition index: 2

Array after Hoare partition: [2, 3, 4, 8, 5]

Complexity Analysis

Time: O(n) because each partition method scans the array once to rearrange elements

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

vs Alternative: Both Lomuto and Hoare are more efficient than naive partitioning that might use extra space; Hoare often performs fewer swaps than Lomuto

Edge Cases

empty array

partition functions will panic or return immediately; code does not handle empty arrays explicitly

DSA Rust

none - no explicit guard for empty array

array with one element

partition returns immediately with index 0 or 0, array unchanged

DSA Rust

none - loop conditions prevent errors

array with all equal elements

Lomuto places pivot at end, Hoare pointers cross quickly; array remains same

DSA Rust

if arr[j] <= pivot in Lomuto loop

When to Use This Pattern

When you need to split an array around a pivot for quicksort, recognize Lomuto uses one pointer to separate smaller elements, while Hoare uses two pointers moving inward to swap out-of-place elements efficiently.

Common Mistakes

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

Mistake: In Hoare partition, not moving pointers correctly causing infinite loops
Fix: Ensure pointers move inside loops and stop when crossing

Summary

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

Use when implementing quicksort to divide and conquer the array efficiently.

Lomuto uses one pointer to track smaller elements; Hoare uses two pointers moving inward to swap misplaced elements.

Practice

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

easy

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

B. Lomuto sorts the array, Hoare reverses it

C. Lomuto works only on sorted arrays, Hoare on unsorted arrays

D. Lomuto uses recursion, Hoare uses iteration

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 that are out of place.

3. Final Answer:

   Lomuto uses a single pointer, Hoare uses two pointers moving inward -> Option A

4. Quick Check:

   Partition pointers = single vs two [OK]

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

Common Mistakes:

• Confusing which partition uses one or two pointers
• Thinking both partitions use the same pointer strategy
• Assuming Hoare partition sorts the array directly

2. Which of the following is the correct Rust function signature for Lomuto partition on a mutable slice of integers?

easy

A. fn lomuto_partition(arr: &mut Vec<i32>, low: i32, high: i32) -> usize

B. fn lomuto_partition(arr: &[i32], low: usize, high: usize) -> usize

C. fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize

D. fn lomuto_partition(arr: &mut [i32], low: i32, high: i32) -> i32

Solution

1. Step 1: Identify mutability and types

   Lomuto partition modifies the array, so it needs a mutable slice &mut [i32]. Indices are usize in Rust for slices.

2. Step 2: Check return type

   Partition returns the pivot index, which is usize to match slice indexing.

3. Final Answer:

   fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize -> Option C

4. Quick Check:

   Mutable slice + usize indices = fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize [OK]

Hint: Mutable slice and usize indices for Rust array partitions [OK]

Common Mistakes:

• Using immutable slice &[] when mutation is needed
• Using i32 for indices instead of usize
• Returning wrong type for pivot index

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

medium

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

B. [2, 3, 7, 6, 8] with pivot index 0

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

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

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot is last element 2. Start i at low-1 = -1 (conceptually), j iterates from low to high-1.

2. Step 2: Iterate and swap

   Check each element: 8 > 2 no swap, 3 > 2 no swap, 7 > 2 no swap, 6 > 2 no swap. Finally swap pivot with element at i+1 = 0.

3. Final Answer:

   [2, 3, 7, 6, 8] with pivot index 0 -> Option B

4. Quick Check:

   Pivot 2 placed at index 0 [OK]

Hint: Pivot ends at correct position after swaps [OK]

Common Mistakes:

• Not swapping pivot to correct place
• Confusing pivot index with array values
• Assuming array is fully sorted after partition

4. Identify the bug in this Hoare partition Rust code snippet:

fn hoare_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
    let pivot = arr[low];
    let mut i = low - 1;
    let mut j = high + 1;
    loop {
        loop { i += 1; if arr[i] >= pivot { break; } }
        loop { j -= 1; if arr[j] <= pivot { break; } }
        if i >= j { return j; }
        arr.swap(i, j);
    }
}

medium

A. Pivot should be last element, not first

B. Loops should use <= and >= reversed

C. Swap should happen after checking i >= j

D. Using usize for i and j causes underflow when subtracting 1

Solution

1. Step 1: Analyze pointer initialization

   i is initialized as low - 1 and j as high + 1, but usize cannot be negative, so low - 1 causes underflow.

2. Step 2: Understand Rust usize behavior

   usize is unsigned, subtracting 1 from 0 wraps to max usize value, causing runtime errors or wrong behavior.

3. Final Answer:

   Using usize for i and j causes underflow when subtracting 1 -> Option D

4. Quick Check:

   Unsigned underflow = bug [OK]

Hint: Unsigned usize cannot go below zero [OK]

Common Mistakes:

• Ignoring underflow in unsigned integers
• Assuming pivot must be last element
• Swapping before checking pointers cross

5. Given an array [10, 80, 30, 90, 40, 50, 70], which partition scheme (Lomuto or Hoare) will perform fewer swaps during the first partition step with pivot as last element (70)?

hard

A. Hoare partition performs fewer swaps

B. Cannot determine without full quicksort

C. Both perform the same number of swaps

D. Lomuto partition performs fewer swaps

Solution

1. Step 1: Understand swap behavior of Lomuto

   Lomuto swaps every time it finds an element smaller than pivot, plus one final swap for pivot placement.

2. Step 2: Understand swap behavior of Hoare

   Hoare swaps only when two pointers find elements on wrong sides, often fewer swaps than Lomuto.

3. Step 3: Apply to given array

   For this array, Lomuto will swap multiple times moving smaller elements forward; Hoare will swap fewer pairs crossing pointers.

4. Final Answer:

   Hoare partition performs fewer swaps -> Option A

5. Quick Check:

   Hoare swaps fewer times [OK]

Hint: Hoare usually swaps less than Lomuto [OK]

Common Mistakes:

• Assuming Lomuto always swaps less
• Ignoring pointer crossing logic in Hoare
• Thinking swap count equals number of elements