Quick Sort Partition Lomuto and Hoare in DSA Rust - Execution Trace

Concept Flow - Quick Sort Partition Lomuto and Hoare

Choose pivot element

↓

Initialize pointers

↓

Compare elements with pivot

↓

Lomuto: Move smaller elements left

↓

Swap elements

↓

Increment pointer

↓

Hoare: Move pointers inward

↓

Swap elements if needed

↓

Pointers cross?

No: Repeat↓

Return partition index

↩No: Repeat

The partition step picks a pivot and rearranges elements so smaller ones go left and larger ones right, using Lomuto or Hoare method.

Execution Sample

DSA Rust

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

This code partitions the array using Lomuto scheme by moving smaller elements left and placing pivot correctly.

Execution Table

Step	Operation	Pointers (i, j)	Array State	Action/Swap	Pivot
1	Choose pivot	-	[9, 3, 7, 6, 2]	-	2 (arr[4])
2	Initialize i	i=0, j=0	[9, 3, 7, 6, 2]	-	2
3	Compare arr[j] < pivot	i=0, j=0	[9, 3, 7, 6, 2]	9 < 2? No	2
4	Compare arr[j] < pivot	i=0, j=1	[9, 3, 7, 6, 2]	3 < 2? No	2
5	Compare arr[j] < pivot	i=0, j=2	[9, 3, 7, 6, 2]	7 < 2? No	2
6	Compare arr[j] < pivot	i=0, j=3	[9, 3, 7, 6, 2]	6 < 2? No	2
7	Swap pivot with arr[i]	i=0	[9, 3, 7, 6, 2]	Swap arr[0] and arr[4]	2
8	Partition index returned	i=0	[2, 3, 7, 6, 9]	Pivot placed at index 0	2
9	Hoare partition start	low=0, high=4, i=0, j=4	[2, 3, 7, 6, 9]	-	2 (arr[0])
10	Move i right while arr[i]<pivot	i=0	[2, 3, 7, 6, 9]	2 < 2? No, i stays	2
11	Move j left while arr[j]>pivot	j=4	[2, 3, 7, 6, 9]	9 > 2? Yes, j=3	2
12	Move j left	j=3	[2, 3, 7, 6, 9]	6 > 2? Yes, j=2	2
13	Move j left	j=2	[2, 3, 7, 6, 9]	7 > 2? Yes, j=1	2
14	Move j left	j=1	[2, 3, 7, 6, 9]	3 > 2? Yes, j=0	2
15	Pointers cross? i=0, j=0	i=0, j=0	[2, 3, 7, 6, 9]	i >= j, partition done	2
16	Return partition index	j=0	[2, 3, 7, 6, 9]	Partition index = 0	2

💡 Lomuto ends when j reaches high-1 and pivot is placed; Hoare ends when pointers cross.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
i	0	0	0	0	0	0	0
j	0	0	1	2	3	-	-
Array	[9,3,7,6,2]	[9,3,7,6,2]	[9,3,7,6,2]	[9,3,7,6,2]	[9,3,7,6,2]	[2,3,7,6,9]	[2,3,7,6,9]

Key Moments - 3 Insights

Why does Lomuto partition swap pivot at the end instead of during the loop?

Because Lomuto moves all smaller elements to the left first, then places pivot at the correct position after the loop (see Step 7 in execution_table).

In Hoare partition, why do pointers stop moving when they cross?

Pointers crossing means all elements are partitioned correctly; continuing would swap elements back incorrectly (see Step 15).

Why does Lomuto use one pointer 'i' but Hoare uses two pointers 'i' and 'j'?

Lomuto uses 'i' to track boundary of smaller elements; Hoare uses 'i' and 'j' to scan from both ends for swaps (see variable_tracker and execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after Step 7 (Lomuto swap)?

A [2, 3, 7, 6, 9]

B [9, 3, 7, 6, 2]

C [3, 2, 7, 6, 9]

D [2, 7, 3, 6, 9]

💡 Hint

Check the 'Array State' column at Step 7 in execution_table.

At which step do the Hoare pointers cross, ending the partition?

A Step 13

B Step 15

C Step 11

D Step 9

💡 Hint

Look for 'Pointers cross' note in execution_table rows.

If the pivot in Lomuto partition was the first element instead of last, how would the pointer 'i' initialization change?

A i would start at low + 1

B i would start at low

C i would start at high

D i would start at zero always

💡 Hint

Consider how Lomuto uses 'i' to track smaller elements after pivot position.

Concept Snapshot

Quick Sort Partition splits array around a pivot.
Lomuto: pivot last element, one pointer i tracks smaller elements.
Hoare: pivot first element, two pointers i and j move inward.
Lomuto swaps pivot at end; Hoare swaps during pointer moves.
Partition returns index dividing smaller and larger elements.

Full Transcript

Quick Sort partition rearranges elements around a pivot. Lomuto partition picks the last element as pivot, uses one pointer 'i' to track smaller elements, and swaps pivot at the end. Hoare partition picks the first element as pivot, uses two pointers 'i' and 'j' moving inward, swapping elements until pointers cross. The execution table shows step-by-step pointer movements, comparisons, swaps, and array states for both methods. Key moments clarify why Lomuto swaps pivot last, why Hoare stops when pointers cross, and the role of pointers in each method. The visual quiz tests understanding of array states and pointer behavior during partitioning.

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