Quick Sort Partition Lomuto and Hoare in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to select the pivot as the last element in Lomuto partition.

DSA C#

int pivot = arr[[1]];

Drag options to blanks, or click blank then click option'

Ahigh

Blow

C0

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the first element as pivot instead of the last.

Using an incorrect index like 'mid' or 'low'.

In Lomuto partition, the pivot is chosen as the last element, which is at index 'high'.

2fill in blank

medium

Complete the code to swap elements in Lomuto partition when arr[j] is less than or equal to pivot.

DSA C#

if (arr[j] <= pivot) {
    i++;
    Swap(arr, i, [1]);
}

Drag options to blanks, or click blank then click option'

Ai

Bhigh

Cpivot

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with the pivot index instead of j.

Swapping with i itself, which does nothing.

We swap arr[i] and arr[j] when arr[j] is less than or equal to pivot to move smaller elements to the left.

3fill in blank

hard

Fix the error in the Hoare partition loop condition to avoid infinite loop.

DSA C#

while (arr[i] [1] pivot) i++;
while (arr[j] [2] pivot) j--;

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or >= causes infinite loops or wrong partitioning.

Swapping the comparison operators between i and j loops.

In Hoare partition, we move i forward while arr[i] is less than pivot, and move j backward while arr[j] is greater than pivot.

4fill in blank

hard

Fill both blanks to correctly swap and return the partition index in Lomuto partition.

DSA C#

Swap(arr, i + 1, [1]);
return [2] + 1;

Drag options to blanks, or click blank then click option'

Ahigh

Blow

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Returning low or j instead of i + 1.

Swapping with wrong index instead of high.

After partitioning, swap the element after i with the pivot at high, then return i + 1 as the partition index.

5fill in blank

hard

Fill all three blanks to correctly implement the Hoare partition swap and return index.

DSA C#

if (i >= j) return [1];
Swap(arr, [2], [3]);

Drag options to blanks, or click blank then click option'

Aj

Bi

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Returning i instead of j.

Swapping with wrong indices or pivot.

In Hoare partition, if i >= j, return j as partition index; otherwise swap arr[i] and arr[j].

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