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

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are working on sorting a list of numbers quickly. To do this, you will learn two ways to split the list into parts: Lomuto partition and Hoare partition. This helps the quick sort algorithm work faster.

🎯 Goal: Build two functions in C# that split a list of numbers using Lomuto and Hoare partition methods. Then, show how the list looks after each partition.

📋 What You'll Learn

Create an integer array called numbers with these exact values: 8, 3, 7, 6, 2, 5, 4, 1

Create an integer variable called pivotIndex and set it to numbers.Length - 1

Write a method called LomutoPartition that takes an integer array and two integers low and high, and returns an integer

Write a method called HoarePartition that takes an integer array and two integers low and high, and returns an integer

Use LomutoPartition on the numbers array from 0 to pivotIndex and print the array after partition

Reset the numbers array to original values, use HoarePartition on it from 0 to pivotIndex and print the array after partition

💡 Why This Matters

🌍 Real World

Quick sort is a fast sorting method used in many software systems to organize data efficiently.

💼 Career

Understanding partition methods helps in optimizing sorting algorithms, which is important for software developers and data engineers.

1

Create the initial array

Create an integer array called numbers with these exact values: 8, 3, 7, 6, 2, 5, 4, 1

DSA C#

# Create the array called numbers with the given values
# Your code here

Hint

Use int[] numbers = {8, 3, 7, 6, 2, 5, 4, 1}; to create the array.

2

Add pivot index variable

Create an integer variable called pivotIndex and set it to numbers.Length - 1

DSA C#

int[] numbers = {8, 3, 7, 6, 2, 5, 4, 1};
# Create pivotIndex variable as numbers.Length - 1
# Your code here

Hint

Use int pivotIndex = numbers.Length - 1; to get the last index.

3

Write Lomuto partition method

Write a method called LomutoPartition that takes an integer array arr and two integers low and high. It should use the Lomuto partition scheme and return the pivot index as an integer.

DSA C#

int[] numbers = {8, 3, 7, 6, 2, 5, 4, 1};
int pivotIndex = numbers.Length - 1;

// Write LomutoPartition method below
# Your code here

Hint

The Lomuto partition picks the last element as pivot and moves smaller elements left.

4

Write Hoare partition method and print results

Write a method called HoarePartition that takes an integer array arr and two integers low and high. It should use the Hoare partition scheme and return the pivot index as an integer. Then, use LomutoPartition on numbers from 0 to pivotIndex and print the array after partition. Reset numbers to original values, use HoarePartition on it from 0 to pivotIndex and print the array after partition.

DSA C#

int[] numbers = {8, 3, 7, 6, 2, 5, 4, 1};
int pivotIndex = numbers.Length - 1;

int LomutoPartition(int[] arr, int low, int high)
{
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp1 = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp1;
    return i + 1;
}

// Write HoarePartition method and print results below
# Your code here

Hint

The Hoare partition picks the first element as pivot and moves elements around it.

Print the array after each partition using Console.WriteLine(string.Join(", ", array)).

Practice

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

easy

A. Lomuto uses recursion, Hoare uses iteration

B. Lomuto sorts the array, Hoare reverses the array

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

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

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, Hoare uses two pointers moving inward -> Option C

4. Quick Check:

   Partition schemes differ by pointer usage = A [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking both use the same pointer approach
• Assuming Hoare always picks first element as pivot

2. Which of the following is the correct C# syntax to swap two elements in an array arr at indices i and j?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. arr.Swap(i, j);

C. swap(arr[i], arr[j]);

D. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

Solution

1. Step 1: Understand swapping in C# arrays

   Swapping requires a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   The option "arr[i] = arr[j]; arr[j] = arr[i];" overwrites arr[i] before saving its value. "int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;" correctly uses a temp variable. "swap(arr[i], arr[j]);" and "arr.Swap(i, j);" are invalid syntax in C#.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option D

4. Quick Check:

   Use temp variable for swap = B [OK]

Hint: Always use a temp variable to swap array elements [OK]

Common Mistakes:

• Overwriting one element before saving it
• Using non-existent swap functions
• Confusing syntax with other languages

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

medium

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

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

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

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

Solution

1. Step 1: Identify pivot and initialize pointers

   Pivot is 2 (last element). Initialize i = -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. Finally swap pivot with arr[i+1] = arr[0].

3. Step 3: Final array after swap

   Swap arr[0] and arr[4]: [2, 3, 7, 6, 8]

4. Final Answer:

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

5. Quick Check:

   Lomuto partitions around pivot = D [OK]

Hint: Pivot ends at correct place after Lomuto partition [OK]

Common Mistakes:

• Swapping incorrectly during iteration
• Confusing pivot position after partition
• Mixing Hoare and Lomuto steps

4. Identify the error in this Hoare partition code snippet in C#:

int HoarePartition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    while (true) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i >= j) return j;
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
}

medium

A. Pivot should be last element, not first

B. Pointers i and j can go out of array bounds causing runtime error

C. Return statement should be i, not j

D. Swap should happen before checking i >= j

Solution

1. Step 1: Analyze pointer increments

   i increments while arr[i] < pivot without boundary check; similarly j decrements without boundary check.

2. Step 2: Identify risk of out-of-bounds

   If all elements are less or greater than pivot, i or j can move beyond array limits causing runtime error.

3. Final Answer:

   Pointers i and j can go out of array bounds causing runtime error -> Option B

4. Quick Check:

   Missing boundary checks cause errors = A [OK]

Hint: Always check array bounds when moving pointers [OK]

Common Mistakes:

• Ignoring boundary checks in loops
• Assuming pivot must be last element
• Misplacing swap and return statements

5. Given the array arr = [10, 80, 30, 90, 40, 50, 70], what is the array state after applying Hoare partition with pivot as arr[low] (first element)?

hard

A. [70, 30, 40, 50, 10, 80, 90]

B. [10, 80, 30, 90, 40, 50, 70]

C. [40, 30, 10, 50, 70, 80, 90]

D. [50, 30, 40, 10, 70, 80, 90]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = 10 (arr[0]), i = low + 1 = 1, j = high = 6 (following the Hoare code style).

2. Step 2: Move pointers inward and swap

   i moves forward while arr[i] < pivot: arr[1]=80 not <10, i stays 1. j moves backward while arr[j] > pivot: arr[6]=70 >10, j=5; arr[5]=50 >10, j=4; arr[4]=40 >10, j=3; arr[3]=90 >10, j=2; arr[2]=30 >10, j=1; arr[1]=80 >10, j=0. Now i=1, j=0, i >= j, so partition ends. But before that, swaps happen when i < j. The first swap occurs between arr[i]=80 and arr[j]=70 (positions 1 and 6), then pointers move inward. After completing swaps, the array becomes [70, 30, 40, 50, 10, 80, 90].

3. Step 3: Resulting array after partition

   The array after Hoare partition is [70, 30, 40, 50, 10, 80, 90].

4. Final Answer:

   [70, 30, 40, 50, 10, 80, 90] -> Option A

5. Quick Check:

   Hoare partitions around first element pivot = B [OK]

Hint: Hoare swaps inward around first element pivot [OK]

Common Mistakes:

• Assuming pivot moves to final position immediately
• Confusing Lomuto and Hoare partition results
• Not tracing pointer movements carefully