Quick Sort Partition Lomuto and Hoare in DSA C# - Execution Trace

Concept Flow - Quick Sort Partition Lomuto and Hoare

Choose pivot = last element

↓

Initialize i = low - 1

↓

For j from low to high-1

↓

If arr[j

↓

i++, swap arr[i

↓

After loop, swap arr[i+1

↓

Return i+1 as pivot index

↓

Choose pivot = arr[low

↓

i = low - 1, j = high + 1

↓

Repeat forever

↓

Increment i until arr[i

↓

Decrement j until arr[j

↓

If i >= j, return j

↓

Else swap arr[i

Lomuto picks last element as pivot and partitions by swapping smaller elements forward. Hoare picks first element as pivot and uses two pointers moving inward to swap out-of-place elements.

Execution Sample

DSA C#

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, j);
    }
  }
  Swap(arr, i + 1, high);
  return i + 1;
}

This code partitions the array using Lomuto scheme by moving elements smaller than pivot to the left and returns pivot index.

Execution Table

Step	Operation	i	j	Pivot	Array State	Pointer Changes
1	Initialize i = low - 1	-1	-	5	[3, 8, 2, 5, 1, 4]	i = -1
2	j = 0, arr[j] = 3 <= 5?	-1	0	5	[3, 8, 2, 5, 1, 4]	Yes
3	arr[j] <= pivot, i++ and swap arr[i], arr[j]	0	0	5	[3, 8, 2, 5, 1, 4]	i=0, swap arr[0], arr[0] (no change)
4	j = 1, arr[j] = 8 <= 5?	0	1	5	[3, 8, 2, 5, 1, 4]	No
5	j = 2, arr[j] = 2 <= 5?	0	2	5	[3, 8, 2, 5, 1, 4]	Yes
6	i++ and swap arr[i], arr[j]	1	2	5	[3, 2, 8, 5, 1, 4]	i=1, swap arr[1], arr[2]
7	j = 3, arr[j] = 5 <= 5?	1	3	5	[3, 2, 8, 5, 1, 4]	Yes
8	i++ and swap arr[i], arr[j]	2	3	5	[3, 2, 5, 8, 1, 4]	i=2, swap arr[2], arr[3]
9	j = 4, arr[j] = 1 <= 5?	2	4	5	[3, 2, 5, 8, 1, 4]	Yes
10	i++ and swap arr[i], arr[j]	3	4	5	[3, 2, 5, 1, 8, 4]	i=3, swap arr[3], arr[4]
11	j = 5, arr[j] = 4 <= 5?	3	5	5	[3, 2, 5, 1, 8, 4]	Yes
12	i++ and swap arr[i], arr[j]	4	5	5	[3, 2, 5, 1, 4, 8]	i=4, swap arr[4], arr[5]
13	After loop, swap arr[i+1], arr[high]	4	-	5	[3, 2, 5, 1, 4, 8]	swap arr[5], arr[5] (no change)
14	Return pivot index i+1	4	-	5	[3, 2, 5, 1, 4, 8]	Pivot index = 5
15	Hoare Partition start	-1	6	3	[3, 2, 5, 1, 4, 8]	i=-1, j=6
16	Increment i until arr[i]>=pivot	2	6	3	[3, 2, 5, 1, 4, 8]	i=0 (arr[0]=3>=3)
17	Decrement j until arr[j]<=pivot	2	3	3	[3, 2, 5, 1, 4, 8]	j=5 (arr[5]=8>3), j=4 (arr[4]=4>3), j=3 (arr[3]=1<=3)
18	i < j? 2 < 3 yes, swap arr[i], arr[j]	2	3	3	[3, 2, 1, 5, 4, 8]	swap arr[2], arr[3]
19	Increment i until arr[i]>=pivot	3	3	3	[3, 2, 1, 5, 4, 8]	i=3 (arr[3]=5>=3)
20	Decrement j until arr[j]<=pivot	3	2	3	[3, 2, 1, 5, 4, 8]	j=2 (arr[2]=1<=3)
21	i >= j? 3 >= 2 yes, return j	3	2	3	[3, 2, 1, 5, 4, 8]	Partition index = 2

💡 Lomuto ends after swapping pivot to correct position; Hoare ends when pointers cross (i >= j)

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	After Step 15	After Step 18	After Step 21
i	-1	0	1	2	3	4	5	-1	2	3
j	-	0	2	3	4	5	-	6	3	2
Pivot (Lomuto)	5	5	5	5	5	5	5	-	-	-
Pivot (Hoare)	-	-	-	-	-	-	-	3	3	3
Array	[3,8,2,5,1,4]	[3,8,2,5,1,4]	[3,2,8,5,1,4]	[3,2,5,8,1,4]	[3,2,5,1,8,4]	[3,2,5,1,4,8]	[3,2,5,1,4,8]	[3,2,5,1,4,8]	[3,2,1,5,4,8]	[3,2,1,5,4,8]

Key Moments - 3 Insights

Why does Lomuto partition use i = low - 1 instead of starting at low?

Because i tracks the last position where a smaller element than pivot was placed. Starting at low - 1 means no smaller elements found yet. See execution_table step 1 and 3 where i increments before swapping.

In Hoare partition, why do we stop when i >= j?

Because i and j pointers have crossed, meaning all elements left of j are less or equal to pivot and right of i are greater or equal. Partitioning is complete. See execution_table step 21.

Why does Lomuto swap pivot at the end with arr[i+1]?

Because i points to last smaller element, so i+1 is the correct pivot position to separate smaller and larger elements. See execution_table step 13.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the array state after swapping?

A [3, 8, 2, 5, 1, 4]

B [3, 2, 8, 5, 1, 4]

C [3, 2, 5, 8, 1, 4]

D [3, 2, 1, 5, 4, 8]

💡 Hint

Check the 'Array State' column at step 6 in execution_table.

At which step in the Hoare partition does the first swap happen?

A Step 18

B Step 17

C Step 19

D Step 21

💡 Hint

Look for 'swap' in the 'Pointer Changes' column for Hoare partition steps.

If in Lomuto partition the pivot was chosen as the first element instead of last, how would the initial i value change?

A i would start at low - 1

B i would start at high

C i would start at low

D i would start at 0

💡 Hint

Recall that i tracks last smaller element index; pivot position affects initial i. See key_moments about i initialization.

Concept Snapshot

Quick Sort Partition Schemes:
- Lomuto: pivot = last element
- i starts at low-1, j scans low to high-1
- Swap smaller elements forward, then pivot
- Hoare: pivot = first element
- i from low-1, j from high+1
- Move i right until >= pivot
- Move j left until <= pivot
- Swap arr[i], arr[j] until i >= j
- Return partition index
- Both rearrange array around pivot for recursive sort

Full Transcript

This visual execution shows how Lomuto and Hoare partition schemes work in Quick Sort. Lomuto picks the last element as pivot and uses a pointer i to track the boundary of smaller elements. It scans the array with j, swapping elements smaller than or equal to pivot forward. After scanning, it swaps the pivot to its correct position and returns the pivot index. Hoare picks the first element as pivot and uses two pointers i and j starting outside the array bounds. i moves right until it finds an element not less than pivot, j moves left until it finds an element not greater than pivot. If i is less than j, they swap elements and continue. When i crosses j, partitioning ends and j is returned as partition index. The execution table traces each step with array states and pointer changes. Variable tracker shows how i, j, pivot, and array change over time. Key moments clarify common confusions about pointer initialization and stopping conditions. Visual quiz tests understanding of array states and pointer movements. The snapshot summarizes the key rules and differences between Lomuto and Hoare partitions.

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