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 = low to high-1

↓

If arr[j

↓

Increment i

↓

Swap arr[i

↓

After loop, swap arr[i+1

↓

Return i+1 as pivot index

↓

Choose pivot = arr[low

↓

Initialize 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

↓

Repeat

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

This code partitions the array using Lomuto scheme by moving elements smaller than pivot to the front and placing pivot in correct position.

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 <= pivot(5)?	-1	0	5	[3, 8, 2, 5, 1, 4]	Yes, i=0; swap arr[0], arr[0] (no change)
3	j=1, arr[j]=8 <= pivot(5)?	0	1	5	[3, 8, 2, 5, 1, 4]	No, i=0
4	j=2, arr[j]=2 <= pivot(5)?	0	2	5	[3, 8, 2, 5, 1, 4]	Yes, i=1; swap arr[1], arr[2] -> [3, 2, 8, 5, 1, 4]
5	j=3, arr[j]=5 <= pivot(5)?	1	3	5	[3, 2, 8, 5, 1, 4]	Yes, i=2; swap arr[2], arr[3] -> [3, 2, 5, 8, 1, 4]
6	j=4, arr[j]=1 <= pivot(5)?	2	4	5	[3, 2, 5, 8, 1, 4]	Yes, i=3; swap arr[3], arr[4] -> [3, 2, 5, 1, 8, 4]
7	End loop, swap arr[i+1], arr[high]	3	-	5	[3, 2, 5, 1, 4, 8]	Swap arr[4], arr[5]
8	Return pivot index i+1	4	-	5	[3, 2, 5, 1, 4, 8]	Pivot index = 4
9	Hoare init i=low-1, j=high+1	-1	6	3	[3, 2, 5, 1, 4, 8]	i=-1, j=6
10	Increment i until arr[i]>=pivot	0	6	3	[3, 2, 5, 1, 4, 8]	i=0 (arr[0]=3 >=3)
11	Decrement j until arr[j]<=pivot	0	5	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)
12	i < j? 0 < 3	0	3	3	[3, 2, 5, 1, 4, 8]	Yes, swap arr[0], arr[3] -> [1, 2, 5, 3, 4, 8]
13	Increment i until arr[i]>=pivot	1	3	3	[1, 2, 5, 3, 4, 8]	i=1 (arr[1]=2 <3), i=2 (arr[2]=5 >=3)
14	Decrement j until arr[j]<=pivot	2	2	3	[1, 2, 5, 3, 4, 8]	j=2 (arr[2]=5 >3), j=1 (arr[1]=2 <=3)
15	i < j? 2 < 1	2	1	3	[1, 2, 5, 3, 4, 8]	No, return j=1
16	Partition done, pivot index = 1	2	1	3	[1, 2, 5, 3, 4, 8]	Hoare partition index = 1

💡 Lomuto ends after placing pivot at correct position; Hoare ends when i >= j and returns partition index.

Variable Tracker

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

Key Moments - 3 Insights

Why does Lomuto partition use i = low - 1 at start?

Because i tracks the last position where a smaller or equal element was placed. Starting at low-1 means no elements placed yet. See execution_table rows 1-2 where i increments before swapping.

Why does Hoare partition return j instead of i?

Because j marks the boundary where elements to the left are <= pivot and to the right are >= pivot. When i >= j, partitioning is done. See execution_table row 15 where i=2, j=1 and j is returned.

Why does Lomuto swap pivot at the end, but Hoare swaps during partition?

Lomuto places pivot last after moving smaller elements forward. Hoare swaps elements out of place during scanning to group smaller and larger elements around pivot. See execution_table rows 7 (Lomuto swap pivot) and 12 (Hoare swap arr[i], arr[j]).

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check execution_table row 6 under 'Array State' column.

At which step does Hoare partition swap elements for the first time?

A Step 10

B Step 12

C Step 14

D Step 15

💡 Hint

Look at execution_table row 12 describing swap operation.

If pivot in Lomuto partition was chosen as arr[low] instead of arr[high], how would the initial i value change?

A i would start at low

B i would start at low - 1

C i would start at high

D i would start at 0

💡 Hint

Recall Lomuto starts i at low-1 because pivot is last element; changing pivot to first means i starts at low.

Concept Snapshot

Quick Sort Partition Schemes:
- Lomuto: pivot = last element
- i starts at low-1, j scans low to high-1
- Swap arr[i+1] with pivot at end
- Hoare: pivot = first element
- i = low-1, j = high+1
- Move i right until >= pivot, j left until <= pivot
- Swap arr[i], arr[j] until i >= j
- Lomuto returns i+1, Hoare returns j
- Both partition array around pivot for recursive quicksort

Full Transcript

This visualization shows two popular quick sort partition methods: Lomuto and Hoare. Lomuto chooses 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 or equal to pivot forward. After scanning, it swaps the pivot into its correct position and returns the pivot index. Hoare chooses 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 those elements. When i meets or passes j, partitioning ends and j is returned as the partition index. The execution table traces each step showing pointer movements, swaps, and array states. Variable tracker shows how i, j, pivot, and array change over time. Key moments clarify common confusions about pointer initialization and return values. The visual quiz tests understanding of array states and pointer actions during partitioning. The snapshot summarizes the key differences and steps of Lomuto and Hoare partition schemes.

Practice

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

easy

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

B. Lomuto sorts in descending order, Hoare sorts in ascending order

C. Lomuto uses recursion, Hoare uses iteration

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

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 A

4. Quick Check:

   Lomuto single pointer, Hoare two pointers inward [OK]

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

Common Mistakes:

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

2. Which of the following is the correct Lomuto partition function header in C++?

easy

A. int partition(int arr[], int low, int high)

B. void partition(int arr[], int low, int high)

C. int partition(int arr[], int start, int end, int pivot)

D. bool partition(int arr[], int low, int high)

Solution

1. Step 1: Check return type

   Lomuto partition returns the pivot index as int after partitioning.

2. Step 2: Check parameters

   It takes array, low index, and high index as parameters to partition the subarray.

3. Final Answer:

   int partition(int arr[], int low, int high) -> Option A

4. Quick Check:

   Returns int pivot index, low high params [OK]

Hint: Partition returns pivot index as int with low and high params [OK]

Common Mistakes:

• Using void return type instead of int
• Adding extra pivot parameter unnecessarily
• Returning bool instead of pivot index

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with low=0 and high=4?

medium

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

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

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

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

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot = arr[4] = 2, i = -1 initially.

2. Step 2: Iterate and swap smaller elements

   Check elements from index 0 to 3:
   - arr[0]=8 > 2 no swap
   - arr[1]=3 > 2 no swap
   - arr[2]=7 > 2 no swap
   - arr[3]=6 > 2 no swap
   After loop, swap arr[i+1]=arr[0] and pivot arr[4].

3. Final Answer:

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

4. Quick Check:

   Pivot swapped to front since no smaller elements [OK]

Hint: Pivot last element, swap smaller left, pivot final swap [OK]

Common Mistakes:

• Swapping elements incorrectly during iteration
• Confusing pivot position after partition
• Assuming pivot is first element

4. Identify the bug in this Hoare partition code snippet:

int hoarePartition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low - 1, j = high + 1;
  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    std::swap(arr[i], arr[j]);
  }
}

medium

A. Initialization of i and j is incorrect

B. No bug, code is correct

C. The loop condition should be i > j instead of i >= j

D. Pivot should be arr[high], not arr[low]

Solution

1. Step 1: Verify pointer initialization

   In standard Hoare partition, i starts at low-1 and j at high+1 to work with the do-while loops correctly.

2. Step 2: Check other parts

   Pivot selection arr[low], movement conditions arr[i] < pivot and arr[j] > pivot, i >= j return, and swap are all correct.

3. Final Answer:

   No bug, code is correct -> Option B

4. Quick Check:

   Standard Hoare uses i=low-1, j=high+1 [OK]

Hint: i starts at low, j at high in Hoare partition [OK]

Common Mistakes:

• Setting i and j outside array bounds
• Confusing pivot position with pointer initialization
• Misusing loop exit condition

5. Given the array [10, 80, 30, 90, 40, 50, 70], after applying Hoare partition with low=0 and high=6, what is the resulting array?

hard

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

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

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

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

Solution

1. Step 1: Set pivot and pointers

   Pivot = arr[0] = 10, i = low - 1 = -1, j = high + 1 = 7.

2. Step 2: Move pointers and check swaps

   do {i++;} while (arr[i] < 10): i=0, arr[0]=10 not <10, stop i=0.
   do {j--;} while (arr[j] > 10): j=6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), stop j=0.
   i=0 < j=0 is false, so i >= j, return j=0, no swap.
   But since i == j, partition ends with pivot index 0.
   However, this means no swaps, so array remains same.

3. Step 3: Re-examine pointer movement

   Actually, the do-while loops stop at i=0 and j=0, so no swaps occur.
   Therefore, the array remains unchanged.

4. Final Answer:

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

5. Quick Check:

   All elements ≥ pivot, array unchanged [OK]

Hint: Track i and j moving inward, swap when i < j [OK]

Common Mistakes:

• Swapping after pointers cross
• Misplacing pivot after partition
• Confusing Hoare with Lomuto output