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 left. Hoare picks first element as pivot and uses two pointers moving inward to swap and partition.

Execution Sample

DSA C

int lomuto_partition(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++;
      int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
  }
  int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
  return i+1;
}

Lomuto partition picks last element as pivot and moves smaller elements to left, then places pivot in correct position.

Execution Table

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

💡 Lomuto ends after placing pivot at correct index; Hoare ends when pointers cross (i >= j)

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 10	After Step 13	After Step 16	After Step 19	After Step 22
i (Lomuto)	-1	-1	0	-	-	-	-	-
j (Lomuto)	-	0 to 5	-	-	-	-	-	-
Pivot (Lomuto)	1	1	1	-	-	-	-	-
Array (Lomuto)	[5,3,8,4,2,7,1]	[5,3,8,4,2,7,1]	[1,3,8,4,2,7,5]	-	-	-	-	-
i (Hoare)	-	-	-	-1	0	1	2	3
j (Hoare)	-	-	-	7	6	5	4	3
Pivot (Hoare)	-	-	-	5	5	5	5	5
Array (Hoare)	-	-	-	[5,3,8,4,2,7,1]	[1,3,8,4,2,7,5]	[1,7,8,4,2,3,5]	[1,7,2,4,8,3,5]	[1,7,2,4,8,3,5]

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 row 1 where i = -1 before loop.

Why does Hoare partition return j, not i?

Because j marks the last position where elements are less or equal to pivot. When i >= j, partitioning is done. See execution_table row 22 where i=3, j=3 and j is returned.

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. Swapping places pivot between smaller and larger elements. See execution_table row 8.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after Lomuto partition completes (step 8)?

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

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

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

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

💡 Hint

Check execution_table row 8 under 'Array State' column.

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

A Step 13

B Step 16

C Step 11

D Step 19

💡 Hint

Look at execution_table rows 13 and 16 for swap operations.

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 high + 1

💡 Hint

Refer to variable_tracker for i initialization in Lomuto partition.

Concept Snapshot

Quick Sort Partition:
- Lomuto: pivot = last element
- i starts at low-1, j scans low to high-1
- Swap smaller elements left, then pivot
- Hoare: pivot = first element
- i from left, j from right move inward
- Swap elements crossing pivot
- Lomuto returns i+1, Hoare returns j
- Both partition array for recursive quicksort

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 an index i to track the boundary of smaller elements. It scans the array with j, swapping elements smaller or equal to pivot to the left. 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 >= pivot, j moves left until it finds an element <= pivot. If i < j, they swap elements and continue. When i >= j, partitioning ends and j is returned. 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 like why i starts at low-1 in Lomuto and why Hoare returns j. The visual quiz tests understanding of array states and pointer positions during partitioning. The snapshot summarizes the key rules and differences between 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 recursion, Hoare uses iteration

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

C. Lomuto uses one pointer, Hoare uses two pointers moving inward

D. Lomuto swaps only equal elements, Hoare swaps all elements

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses a single 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 that are on the wrong side.

3. Final Answer:

   Lomuto uses one pointer, Hoare uses two pointers moving inward -> Option C

4. Quick Check:

   Pointer count difference = A [OK]

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

Common Mistakes:

• Confusing sorting order difference
• Thinking both use same pointer method
• Assuming Hoare uses recursion only

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

easy

A. int lomutoPartition(int arr[], int low, int high);

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

C. int lomutoPartition(int arr, int low, int high);

D. int lomutoPartition(int arr[], int high, int low);

Solution

1. Step 1: Check parameter types

   Array must be passed as int arr[], and low and high as int indices.

2. Step 2: Check return type

   Lomuto partition returns an int index, so return type must be int.

3. Final Answer:

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

4. Quick Check:

   Correct signature = A [OK]

Hint: Partition returns index, so return type is int [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int arr instead of int arr[]
• Swapping low and high parameters

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. [8, 3, 7, 6, 2]

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

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

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

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot is arr[high] = 2. Initialize i = low - 1 = -1.

2. Step 2: Iterate and swap elements smaller than pivot

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

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start = A [OK]

Hint: Pivot is last element in Lomuto [OK]

Common Mistakes:

• Swapping elements incorrectly with pivot
• Using wrong pivot index
• Confusing i and j pointers

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 (1) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    swap(&arr[i], &arr[j]);
  }
}

medium

A. Return statement should be i, not j

B. Swap function is missing

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

D. Pointers i and j are initialized incorrectly

Solution

1. Step 1: Examine the swap call

   The code calls swap(&arr[i], &arr[j]); but the swap function is not defined in the snippet, causing a compilation error.

2. Step 2: Verify other components

   Pointer initialization i=low-1, j=high+1 is correct for do-while structure; pivot at low ok; return j standard.

3. Final Answer:

   Swap function is missing -> Option B

4. Quick Check:

   Undefined swap function = C [OK]

Hint: Swap must be defined before calling [OK]

Common Mistakes:

• Missing swap function definition
• Confusing Hoare pointer initialization
• Returning wrong index after partition

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

hard

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

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

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

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

Solution

1. Step 1: Initialize pointers and pivot

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

2. Step 2: Move pointers

   do { i++; } while (arr[i] < 10); i++ to 0, arr[0]=10 not < 10, i=0.
   do { j--; } while (arr[j] > 10); j-- from 7: 6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), j=0.
   i=0 >= j=0, return 0. No swap.

3. Final Answer:

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

4. Quick Check:

   Array unchanged (all ≥ pivot) = D [OK]

Hint: Hoare partition swaps inward until pointers cross [OK]

Common Mistakes:

• Assuming full sort after one partition
• Confusing pivot position after partition
• Mis-tracing pointer movements