Quick Sort Partition Lomuto and Hoare in DSA Javascript - 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, j = high + 1

↓

Repeat forever

↓

j-- while arr[j

↓

i++ while arr[i

↓

If i >= j return j

↓

Else swap arr[i

↩Back to Repeat

Lomuto picks last element as pivot and partitions by moving smaller elements left. Hoare picks first element as pivot and partitions by moving pointers inward and swapping.

Execution Sample

DSA Javascript

function lomutoPartition(arr, low, high) {
  let pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

This code partitions the array using Lomuto scheme, placing elements smaller or equal to pivot on left and returns pivot index.

Execution Table

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

💡 Lomuto ends after placing pivot at correct index; 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	Final
i (Lomuto)	-1	0	1	2	3	4	4
j (Lomuto)	-	0	2	3	4	5	-
Pivot (Lomuto)	5	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,8,1,4]	[3,2,5,1,8,4]	[3,2,5,1,4,8]	[3,2,5,1,4,8]
i (Hoare)	0	-	-	-	-	-	2
j (Hoare)	6	-	-	-	-	-	2
Pivot (Hoare)	3	-	-	-	-	-	3
Array (Hoare)	[3,2,5,1,4,8]	[5,2,3,1,4,8]	[5,2,3,1,4,8]	[5,2,3,1,4,8]	[5,2,3,1,4,8]	[5,2,3,1,4,8]	[5,2,3,1,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 was placed. Starting at low - 1 means no elements placed yet. See execution_table step 1 and 3 where i increments before swapping.

In Hoare partition, why do we decrement j and increment i before swapping?

We move j left until we find element <= pivot and i right until element >= pivot. This ensures elements less than pivot go left, greater go right. See execution_table steps 16-18 for pointer moves and swap.

Why does Hoare partition return j, not i?

Because j is the last index where left side elements are <= pivot. When i >= j, pointers crossed and partitioning is done. Returning j splits array correctly. See execution_table step 21.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of i after step 6 in Lomuto partition?

A 0

B 2

C 1

D -1

💡 Hint

Check the 'i' column in execution_table row with step 6.

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

A Step 18

B Step 16

C Step 20

D Step 21

💡 Hint

Look for 'swap' in the Operation column for Hoare partition steps.

If in Lomuto partition the pivot was chosen as the first element instead of last, how would the pointer i initialization 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 that i tracks last smaller element index; changing pivot position affects i start.

Concept Snapshot

Quick Sort Partition Schemes:
- Lomuto: pivot = last element
  i starts at low-1
  j scans low to high-1
  swap if arr[j] <= pivot
  finally swap pivot to i+1
- Hoare: pivot = first element
  i = low, j = high+1
  move i right while arr[i]<pivot
  move j left while arr[j]>pivot
  swap arr[i], arr[j] if i<j
  else return j
Both partition arrays around pivot for recursive quicksort.

Full Transcript

This visual execution traces two popular quick sort partition methods: Lomuto and Hoare. Lomuto picks the last element as pivot and uses a pointer i starting before low to track smaller elements. It scans with j and swaps elements smaller or equal to pivot to the left. After scanning, it places the pivot after the last smaller element. Hoare picks the first element as pivot and uses two pointers i and j starting inside and outside the array bounds respectively. It moves i right until it finds an element not less than pivot, and j left until it finds an element not greater than pivot, then swaps them. When pointers cross, partitioning ends. The execution table shows step-by-step pointer movements, swaps, and array states for both methods on the example array [3,8,2,5,1,4]. Variable tracker summarizes pointer and array changes. Key moments clarify common confusions about pointer initialization and return values. Visual quiz tests understanding of pointer values and swap steps. The snapshot summarizes the key steps 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 one pointer, Hoare uses two pointers moving inward

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

C. Lomuto is used only for arrays of even length, Hoare for odd length

D. Lomuto swaps elements 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 with the pivot at the end.

2. Step 2: Understand Hoare partition

   Hoare partition uses two pointers starting from both ends moving inward to swap elements out of place.

3. Final Answer:

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

4. Quick Check:

   Pointer count difference = Lomuto(1), Hoare(2) [OK]

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

Common Mistakes:

• Confusing the number of pointers used
• Thinking Lomuto sorts differently by order
• Assuming partition depends on array length

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during partition?

easy

A. 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[i] = arr[j]; arr[j] = arr[i];

Solution

1. Step 1: Identify correct swap syntax in JavaScript

   JavaScript does not support tuple unpacking; swapping requires a temporary variable.

2. Step 2: Check each option

   temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly; B is Python syntax; C is undefined function; D overwrites values incorrectly.

3. Final Answer:

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

4. Quick Check:

   Use temp variable for swap in JS [OK]

Hint: Use temp variable to swap in JS, no tuple unpacking [OK]

Common Mistakes:

• Using Python-style tuple swap in JavaScript
• Calling undefined swap function
• Overwriting values 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 = 2 (last element). i starts at -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 C

5. Quick Check:

   Lomuto partition places pivot correctly [OK]

Hint: Pivot is last element; swap smaller elements left [OK]

Common Mistakes:

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

4. Given this Hoare partition code snippet, what is the bug?

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

medium

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

B. The loop condition should be while(i < j), not while(true)

C. Swap syntax is invalid in JavaScript

D. Initialization of i and j is incorrect; should be i=low, j=high

Solution

1. Step 1: Check initialization of pointers

   Hoare partition requires i = low and j = high to start inside the array.

2. Step 2: Analyze effect of incorrect initialization

   Standard Hoare partition initializes i = low, j = high, starting the pointers at the array bounds and moving inward.

3. Final Answer:

   Initialization of i and j is incorrect; should be i=low, j=high -> Option D

4. Quick Check:

   Correct pointer start = i=low, j=high [OK]

Hint: Start pointers inside array for Hoare partition [OK]

Common Mistakes:

• Setting i and j outside array bounds
• Confusing pivot position
• Misusing swap syntax

5. You want to sort an array using Quick Sort with Hoare partition. Which of these is the correct recursive call pattern after partitioning at index p?

hard

A. quickSort(arr, low, p - 1); quickSort(arr, p, high);

B. quickSort(arr, low, p); quickSort(arr, p + 1, high);

C. quickSort(arr, low, p + 1); quickSort(arr, p, high);

D. quickSort(arr, low, p - 1); quickSort(arr, p + 1, high);

Solution

1. Step 1: Understand Hoare partition return value

   Hoare partition returns an index p such that elements arr[low..p] ≤ pivot and arr[p+1..high] ≥ pivot. The pivot is not guaranteed to be at position p.

2. Step 2: Determine correct recursive calls

   Recurse on the left subarray from low to p (inclusive) and right subarray from p+1 to high: quickSort(arr, low, p); quickSort(arr, p + 1, high).

3. Final Answer:

   quickSort(arr, low, p); quickSort(arr, p + 1, high); -> Option B

4. Quick Check:

   Hoare recursion: low to p, p+1 to high [OK]

Hint: Hoare: quickSort(low, p); quickSort(p+1, high) [OK]

Common Mistakes:

• Using p+1 in left recursive call
• Ignoring infinite recursion risk
• Confusing Lomuto and Hoare recursion