Quick Sort Partition Lomuto and Hoare in DSA Rust - Build from Scratch

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are helping a librarian organize books by their ID numbers. To do this efficiently, you will use the Quick Sort method, focusing on the partition step. This step divides the books into two groups based on a pivot book ID.

🎯 Goal: Build two partition functions in Rust: one using the Lomuto method and one using the Hoare method. These functions will rearrange the list of book IDs around a pivot, preparing the list for sorting.

📋 What You'll Learn

Create a vector called books with the exact values [8, 3, 7, 6, 2, 5, 4, 1]

Create a variable called pivot_index set to 7 to represent the last index of the vector

Write a function called lomuto_partition that takes a mutable slice of i32 and two usize indices low and high, and returns a usize index after partitioning using Lomuto's method

Write a function called hoare_partition that takes a mutable slice of i32 and two usize indices low and high, and returns a usize index after partitioning using Hoare's method

Call both partition functions on the books vector separately and print the vector after each partition to show the rearranged order

💡 Why This Matters

🌍 Real World

Partitioning helps organize data quickly, like sorting books or files by ID or name.

💼 Career

Understanding partition methods is essential for software engineers working on efficient sorting and searching algorithms.

1

Create the initial vector of book IDs

Create a vector called books with the exact values [8, 3, 7, 6, 2, 5, 4, 1]

DSA Rust

# Create the vector books with the given values
# Your code here

Hint

Use let mut books = vec![8, 3, 7, 6, 2, 5, 4, 1]; to create a mutable vector.

2

Set the pivot index for partitioning

Create a variable called pivot_index and set it to 7 to represent the last index of the books vector

DSA Rust

fn main() {
    let mut books = vec![8, 3, 7, 6, 2, 5, 4, 1];
    // Set pivot_index to 7
    // Your code here
}

Hint

Use let pivot_index = 7; to set the pivot index.

3

Write the Lomuto and Hoare partition functions

Write a function called lomuto_partition that takes a mutable slice of i32 and two usize indices low and high, and returns a usize index after partitioning using Lomuto's method. Also write a function called hoare_partition with the same parameters and return type that partitions using Hoare's method.

DSA Rust

fn main() {
    let mut books = vec![8, 3, 7, 6, 2, 5, 4, 1];
    let pivot_index = 7;
}

// Write lomuto_partition function here
// Your code here

// Write hoare_partition function here
// Your code here

Hint

Use the Lomuto method: pivot is last element, move smaller elements left, then place pivot. Use Hoare method: pivot is first element, move indices inward swapping elements.

4

Call partition functions and print results

Call lomuto_partition on the books vector with low = 0 and high = pivot_index, then print books. Reset books to the original vector, call hoare_partition with the same indices, and print books again.

DSA Rust

fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
    // Lomuto partition code
}

fn hoare_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
    // Hoare partition code
}

fn main() {
    let mut books = vec![8, 3, 7, 6, 2, 5, 4, 1];
    let pivot_index = 7;
    // Call lomuto_partition and print books
    // Your code here
    
    // Reset books to original
    // Call hoare_partition and print books
    // Your code here
}

Hint

Call lomuto_partition(&mut books, 0, pivot_index), print books, reset books, then call hoare_partition(&mut books, 0, pivot_index) and print again.

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