Quick Sort Partition Lomuto and Hoare in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on Array

What is the output array after applying Lomuto partition on the given array with pivot as last element?

DSA C#

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

int p = LomutoPartition(arr, 0, arr.Length - 1);
// Print array after partition
string result = string.Join(", ", arr);

A 2, 3, 7, 6, 8

B 2, 3, 6, 7, 8

C 3, 2, 6, 7, 8

D 3, 2, 7, 6, 8

💡 Hint

Remember Lomuto partition places elements smaller or equal to pivot to the left and pivot at the correct position.

Lomuto partition selects the last element as pivot (2). No elements <= 2 before it, so i remains -1 and pivot swaps to front. The final array after partition is [2, 3, 7, 6, 8].

❓ Predict Output

intermediate

Output of Hoare Partition on Array

What is the output array after applying Hoare partition on the given array with pivot as first element?

DSA C#

int[] arr = {8, 3, 7, 6, 2};
int HoarePartition(int[] array, int low, int high) {
    int pivot = array[low];
    int i = low - 1;
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (array[i] < pivot);
        do {
            j--;
        } while (array[j] > pivot);
        if (i >= j) return j;
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

int p = HoarePartition(arr, 0, arr.Length - 1);
// Print array after partition
string result = string.Join(", ", arr);

A 2, 3, 6, 7, 8

B 3, 2, 7, 6, 8

C 2, 3, 7, 6, 8

D 3, 2, 6, 7, 8

💡 Hint

Hoare partition uses the first element as pivot and swaps elements to ensure left side smaller and right side larger.

Hoare partition selects 8 as pivot. It swaps elements to place smaller on left and larger on right. The final array after partition is [2, 3, 7, 6, 8].

🧠 Conceptual

advanced

Difference Between Lomuto and Hoare Partition

Which statement correctly describes a key difference between Lomuto and Hoare partition schemes?

A Lomuto partition always places the pivot at its final sorted position, Hoare partition may not.

B Hoare partition always places the pivot at its final sorted position, Lomuto partition may not.

C Both Lomuto and Hoare partitions always place the pivot at its final sorted position.

D Neither Lomuto nor Hoare partitions place the pivot at its final sorted position.

💡 Hint

Think about where the pivot ends up after partition in each scheme.

Lomuto partition places the pivot at its correct sorted position after partition. Hoare partition only ensures elements are partitioned but pivot may not be at final position.

🔧 Debug

advanced

Identify Error in Lomuto Partition Code

What error will this Lomuto partition code cause when run on array [4, 5, 3, 7, 2]? int LomutoPartition(int[] array, int low, int high) { int pivot = array[high]; int i = low; for (int j = low; j < high; j++) { if (array[j] <= pivot) { int temp = array[i]; array[i] = array[j]; array[j] = temp; i++; } } int temp1 = array[i]; array[i] = array[high]; array[high] = temp1; return i; }

A Incorrect partition because pivot is not swapped at the end

B ArrayIndexOutOfBoundsException due to i starting at low instead of low - 1

C Infinite loop because i is never incremented

D No error; code runs correctly and partitions array

💡 Hint

Check the initialization of i and how it is incremented inside the loop.

Starting i at low and incrementing after swap is a valid Lomuto variant. The code runs correctly and partitions the array.

🚀 Application

expert

Number of Items in Left Partition After Hoare Partition

Given array [10, 80, 30, 90, 40, 50, 70] and Hoare partition with pivot as first element, how many items are guaranteed to be in the left partition after partitioning?

A At least 3 items

B At least 0 items (pivot may be smallest)

C At least 1 item

D At least 2 items

💡 Hint

Consider if pivot is smallest element in the array.

Hoare partition does not guarantee any minimum number of items in left partition. If pivot is smallest, left partition can be empty.

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