Quick Sort Partition Lomuto and Hoare in DSA Java - 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

↓

i++, swap arr[i

↓

Swap arr[i+1

↓

Return i+1 as pivot index

↓

Choose pivot = arr[low

↓

i = low, j = high + 1

↓

Repeat

↓

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

Execution Sample

DSA Java

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

💡 Lomuto ends after swapping pivot to correct position and returns pivot index; Hoare ends when pointers cross and returns partition index.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	After Step 12	After Step 15	After Step 18
i (Lomuto)	-1	0	1	3	3	4	-	-	-	-
j (Lomuto)	-	0	2	4	-	-	-	-	-	-
Pivot (Lomuto)	5	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,8,4]	[3,2,5,1,4,8]	-	-	-	-
i (Hoare)	-	-	-	-	-	-	0	0	2	3
j (Hoare)	-	-	-	-	-	-	6	3	3	2
Pivot (Hoare)	-	-	-	-	-	-	3	3	3	3
Array (Hoare)	-	-	-	-	-	-	[3,2,5,1,4,8]	[1,2,5,3,4,8]	[1,2,3,5,4,8]	[1,2,3,5,4,8]

Key Moments - 3 Insights

Why does Lomuto partition use i = low - 1 initially?

Because i tracks the last position where a smaller or equal element than pivot was placed. Starting at low - 1 means no elements are placed yet. See execution_table step 1 and 2 where i moves from -1 to 0 after first smaller element.

In Hoare partition, why do we increment i and decrement j until conditions are met before swapping?

Because i and j find elements on wrong sides of pivot to swap. Incrementing i stops at element >= pivot, decrementing j stops at element <= pivot. This ensures correct partitioning. See execution_table steps 10-15.

Why does Hoare partition return j instead of i?

Because when pointers cross (i >= j), j marks the boundary of partition. Returning j splits array correctly. See execution_table step 18 where i=3, j=2 and j=2 is returned.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after Lomuto partition 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 the 'Array State' column at step 6 in execution_table.

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

A Step 15

B Step 10

C Step 12

D Step 18

💡 Hint

Look for 'swap' in Pointer Changes column in execution_table for Hoare 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 low

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 shifts 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 left, then pivot
- Returns pivot index

- Hoare: pivot = first element
- i = low, j = high+1
- Move i right until >= pivot
- Move j left until <= pivot
- Swap arr[i], arr[j] if i<j
- Return j when pointers cross

Both partition arrays for recursive quicksort calls.

Full Transcript

This visual execution trace shows how Lomuto and Hoare partition schemes work in quicksort. Lomuto picks the last element as pivot and uses a pointer i starting at low-1 to track smaller elements. It scans the array with j, swapping elements smaller or equal to pivot to the left. Finally, 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 pointers cross, j is returned as partition index. The execution table traces each step with array states and pointer changes, helping learners see how the array is rearranged step-by-step. Key moments clarify common confusions about pointer initialization and return values. The visual quiz tests understanding of array states and pointer movements during partitioning.

Practice

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

easy

A. Lomuto uses one 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 swaps only once, Hoare swaps multiple times

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 out of place.

3. Final Answer:

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

4. Quick Check:

   Pointer count difference [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax to swap elements at indices i and j in Java array arr?

easy

A. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

C. swap(arr[i], arr[j]);

D. arr.swap(i, j);

Solution

1. Step 1: Identify Java swap syntax

   Java does not support tuple unpacking or built-in swap method for arrays, so manual swap using a temporary variable is needed.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable to swap correctly; others are invalid Java syntax.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Manual swap with temp variable [OK]

Hint: Use temp variable to swap array elements in Java [OK]

Common Mistakes:

• Using Python-style tuple swap
• Calling non-existent swap method
• Trying to swap without temp variable

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with pivot as last element?

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: Identify pivot and initialize pointers

   Pivot is last element 2. 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. Then swap pivot with element at i+1 (index 0): swap arr[0] and arr[4].

3. Final Answer:

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

4. Quick Check:

   Lomuto partition output [OK]

Hint: Pivot last element, swap smaller left, pivot to i+1 [OK]

Common Mistakes:

• Not swapping pivot at end
• Confusing pivot position
• Swapping elements incorrectly

4. Find the error in this Hoare partition code snippet:

int hoarePartition(int[] arr, int low, int high) {
  int pivot = arr[low];
  int i = low + 1, j = high;
  while (true) {
    while (i <= high && arr[i] < pivot) i++;
    while (j >= low && arr[j] > pivot) j--;
    if (i >= j) break;
    int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
  }
  int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp;
  return j;
}

medium

A. Pointers i and j initialization is incorrect

B. Pivot should be last element, not first

C. The inner while conditions should use <= and >= incorrectly

D. No error, code is correct

Solution

1. Step 1: Check pointer initialization

   In Hoare partition, i starts at low + 1 and j at high, which is a valid approach.

2. Step 2: Analyze pointer movement and swapping

   The code correctly moves pointers inward and swaps elements until i >= j, then swaps pivot with arr[j].

3. Final Answer:

   No error, code is correct -> Option D

4. Quick Check:

   Pointer start positions and loop logic [OK]

Hint: Hoare pointers start inside range: i=low+1, j=high [OK]

Common Mistakes:

• Starting pointers outside array incorrectly
• Using wrong pivot position
• Misplacing swap after loop

5. Given array arr = [5, 3, 8, 4, 2, 7, 1, 10], after applying Hoare partition with pivot as first element, what is the correct partitioned array?

hard

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

B. [2, 3, 1, 4, 5, 7, 8, 10]

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

D. [5, 3, 8, 4, 2, 7, 1, 10]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = 5 (first element), i = low - 1 = -1, j = high + 1 = 8.

2. Step 2: Move pointers and swap

   i moves right skipping elements < 5: i=0(5), stop; j moves left skipping elements > 5: j=7(10),6(1 stop at 1). Swap arr[i]=5 and arr[j]=1. Array becomes [1,3,8,4,2,7,5,10]. Continue until i >= j.

3. Step 3: Final partitioned array

   After all swaps, array is [2, 3, 1, 4, 5, 7, 8, 10] with pivot index at 4.

4. Final Answer:

   [2, 3, 1, 4, 5, 7, 8, 10] -> Option B

5. Quick Check:

   Hoare partition swaps around pivot [OK]

Hint: Hoare swaps elements crossing pointers around pivot [OK]

Common Mistakes:

• Confusing pivot position after partition
• Not swapping correctly when pointers cross
• Assuming sorted order after one partition