Quick Sort Partition Lomuto and Hoare in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Lomuto partition scheme in Quick Sort?

Lomuto partition picks the last element as pivot and rearranges the array so that elements smaller than pivot come before it, and larger come after. It uses one index to track the boundary between smaller and larger elements.

intermediate

How does the Hoare partition scheme differ from Lomuto's in Quick Sort?

Hoare partition uses two indices starting from both ends of the array moving towards each other, swapping elements that are on the wrong side of the pivot. It usually picks the first element as pivot and is more efficient with fewer swaps.

beginner

In Lomuto partition, what happens after the partitioning is done?

The pivot element is placed in its correct sorted position, and the array is split into two parts: elements less than pivot on the left, and elements greater or equal on the right.

intermediate

Why is Hoare partition considered more efficient than Lomuto partition?

Hoare partition generally does fewer swaps and comparisons because it stops scanning as soon as it finds elements to swap, making it faster especially on large arrays.

advanced

Show the basic Rust code snippet for Lomuto partition function.

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

Which element does Lomuto partition typically choose as pivot?

A First element

B Random element

C Middle element

D Last element

Lomuto partition usually picks the last element as the pivot.

In Hoare partition, what do the two indices do?

A One moves left to right, other right to left

B Both move from left to right

C Both move from right to left

D They stay fixed

Hoare partition uses two indices moving towards each other from opposite ends.

What is the main advantage of Hoare partition over Lomuto?

A More swaps

B Always picks the middle element as pivot

C Fewer swaps and comparisons

D Simpler code

Hoare partition generally does fewer swaps and comparisons, making it more efficient.

After Lomuto partition, where is the pivot placed?

A At its correct sorted position

B At the end of the array

C At the start of the array

D Random position

The pivot is placed at its correct sorted position after partitioning.

Which partition scheme is more suitable for arrays with many duplicate elements?

A Lomuto

B Hoare

C Both are equally suitable

D Neither

Hoare partition handles duplicates more efficiently by reducing unnecessary swaps.

Explain how Lomuto partition works step-by-step.

Think about how the array is rearranged around the pivot.

Describe the differences between Lomuto and Hoare partition schemes.

Focus on how indices move and how elements are swapped.

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