Quick Sort Partition Lomuto and Hoare in DSA C#

Mental Model

Partition divides the array into parts so that smaller values go left and bigger values go right around a pivot.

Analogy: Imagine sorting books on a shelf by height: pick one book as a reference, then move shorter books to the left and taller books to the right.

Array: [5, 3, 8, 4, 2]
Pivot chosen -> 2 (Lomuto) or 5 (Hoare)
Indexes:
Lomuto: i and j move forward
Hoare: i moves right, j moves left

Initial:
[5, 3, 8, 4, 2]
 ↑           ↑
 i           j

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Partition the array using Lomuto and Hoare methods and show how elements rearrange around the pivot

Step 1: Lomuto: choose last element 2 as pivot, start i at -1, j at 0

Array: [5, 3, 8, 4, 2]
i = -1, j = 0, pivot = 2

Why: We pick pivot at end and prepare pointers to rearrange smaller elements left

Step 2: Lomuto: j=0 (5) > pivot(2), no swap, j moves to 1

Array: [5, 3, 8, 4, 2]
i = -1, j = 1

Why: 5 is bigger than pivot, so it stays right

Step 3: Lomuto: j=1 (3) > pivot(2), no swap, j moves to 2

Array: [5, 3, 8, 4, 2]
i = -1, j = 2

Why: 3 is bigger than pivot, stays right

Step 4: Lomuto: j=2 (8) > pivot(2), no swap, j moves to 3

Array: [5, 3, 8, 4, 2]
i = -1, j = 3

Why: 8 bigger than pivot, stays right

Step 5: Lomuto: j=3 (4) > pivot(2), no swap, j moves to 4

Array: [5, 3, 8, 4, 2]
i = -1, j = 4

Why: 4 bigger than pivot, stays right

Step 6: Lomuto: swap pivot(2) with element at i+1 (index 0)

Array: [2, 3, 8, 4, 5]
i = 0

Why: Place pivot in correct position so left are smaller or equal

Step 7: Hoare: choose pivot as first element 5, i=0, j=4

Array: [5, 3, 8, 4, 2]
i = 0, j = 4, pivot = 5

Why: Pivot chosen at start, pointers ready to move inward

Step 8: Hoare: move i right while arr[i] < pivot: i=1 (3 < 5), i=2 (8 > 5 stop)

Array: [5, 3, 8, 4, 2]
i = 2, j = 4

Why: i stops at first element not less than pivot

Step 9: Hoare: move j left while arr[j] > pivot: j=4 (2 < 5 stop)

Array: [5, 3, 8, 4, 2]
i = 2, j = 4

Why: j stops at first element not greater than pivot

Step 10: Hoare: swap arr[i](8) and arr[j](2)

Array: [5, 3, 2, 4, 8]
i = 2, j = 4

Why: Swap to put smaller on left and bigger on right

Step 11: Hoare: move i right while arr[i] < pivot: i=3 (4 < 5), i=4 (8 > 5 stop)

Array: [5, 3, 2, 4, 8]
i = 4, j = 4

Why: i moves to next element not less than pivot

Step 12: Hoare: move j left while arr[j] > pivot: j=3 (4 < 5 stop)

Array: [5, 3, 2, 4, 8]
i = 4, j = 3

Why: j moves to next element not greater than pivot

Step 13: Hoare: since i >= j, partition ends, return j=3

Array: [5, 3, 2, 4, 8]

Why: Pointers crossed, partition done

Result:

Lomuto partitioned array: [2, 3, 8, 4, 5] with pivot index 0
Hoare partitioned array: [5, 3, 2, 4, 8] with partition index 3

Annotated Code

DSA C#

using System;

class QuickSortPartition {
    // Lomuto partition scheme
    public static 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++;
                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // swap pivot to correct position
        int tempPivot = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = tempPivot;
        return i + 1;
    }

    // Hoare partition scheme
    public static int HoarePartition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low - 1;
        int j = high + 1;
        while (true) {
            do {
                i++;
            } while (arr[i] < pivot);

            do {
                j--;
            } while (arr[j] > pivot);

            if (i >= j) {
                return j;
            }

            // swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    static void PrintArray(int[] arr) {
        for (int i = 0; i < arr.Length; i++) {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(", ");
        }
        Console.WriteLine();
    }

    static void Main() {
        int[] arrLomuto = {5, 3, 8, 4, 2};
        int[] arrHoare = {5, 3, 8, 4, 2};

        int lomutoIndex = LomutoPartition(arrLomuto, 0, arrLomuto.Length - 1);
        Console.WriteLine("Lomuto partitioned array:");
        PrintArray(arrLomuto);
        Console.WriteLine("Pivot index: " + lomutoIndex);

        int hoareIndex = HoarePartition(arrHoare, 0, arrHoare.Length - 1);
        Console.WriteLine("Hoare partitioned array:");
        PrintArray(arrHoare);
        Console.WriteLine("Partition index: " + hoareIndex);
    }
}

int pivot = arr[high];

select pivot as last element for Lomuto

int i = low - 1;

initialize i to track smaller elements boundary

for (int j = low; j < high; j++) {

iterate j through array to compare with pivot

if (arr[j] <= pivot) { i++; swap arr[i] and arr[j]; }

move smaller or equal elements left by swapping

swap arr[i + 1] and arr[high];

place pivot after smaller elements

int pivot = arr[low];

select pivot as first element for Hoare

do { i++; } while (arr[i] < pivot);

move i right until element >= pivot

do { j--; } while (arr[j] > pivot);

move j left until element <= pivot

if (i >= j) return j;

stop when pointers cross

swap arr[i] and arr[j];

swap elements to correct sides

Output

Lomuto partitioned array:

2, 3, 8, 4, 5

Pivot index: 0

Hoare partitioned array:

5, 3, 2, 4, 8

Partition index: 3

Complexity Analysis

Time: O(n) because each partition scans the array segment once

Space: O(1) because partitioning is done in place without extra arrays

vs Alternative: Both Lomuto and Hoare partition schemes are more efficient than naive methods that create new arrays; Hoare often performs fewer swaps than Lomuto

Edge Cases

array with all equal elements

Lomuto places pivot at end but all elements equal, Hoare partitions but pointers cross quickly

DSA C#

if (arr[j] <= pivot) { i++; swap arr[i] and arr[j]; }

array with single element

partition returns immediately with pivot index as low or high

DSA C#

for (int j = low; j < high; j++) { ... }

array sorted ascending

Lomuto swaps many elements, Hoare moves pointers quickly

DSA C#

do { i++; } while (arr[i] < pivot);

When to Use This Pattern

When you need to split an array around a pivot for quicksort, recognize the partition step and choose Lomuto or Hoare to rearrange elements efficiently.

Common Mistakes

Mistake: Using Lomuto partition but forgetting to swap the pivot at the end
Fix: Always swap the pivot element with the element at i+1 after the loop

Mistake: In Hoare partition, not moving pointers correctly causing infinite loop
Fix: Ensure i moves right while less than pivot and j moves left while greater than pivot before swapping

Summary

Partitions an array around a pivot so smaller elements go left and larger go right.

Use when implementing quicksort to efficiently divide the array for recursive sorting.

The key is how pointers move and swap elements to place the pivot correctly.

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