Quick Sort Partition Lomuto and Hoare in DSA Javascript

Mental Model

Partition splits an array into parts so smaller values go left and bigger go right around a pivot.

Analogy: Imagine sorting books on a shelf by height: pick one book as a pivot, then move shorter books to the left and taller books to the right.

Array: [7, 2, 5, 3, 9]
Pivot chosen -> 9
Lomuto partition:
[7, 2, 5, 3, 9]
 ↑           ↑
 i           j
Hoare partition:
[7, 2, 5, 3, 9]
 ↑           ↑
 left        right

Dry Run Walkthrough

Input: array: [7, 2, 5, 3, 9], partition using Lomuto and Hoare

Goal: Show how Lomuto and Hoare partition rearrange the array around a pivot

Step 1: Lomuto: choose last element 9 as pivot, start i at low-1 = -1

[7, 2, 5, 3, 9]
i = -1, j = 0

Why: We pick pivot at end and i tracks last smaller element

Step 2: Lomuto: j=0, 7 <= 9, increment i to 0, swap arr[i] and arr[j]

[7, 2, 5, 3, 9]
i = 0, j = 0

Why: 7 is smaller than pivot, so move it to left side

Step 3: Lomuto: j=1, 2 <= 9, increment i to 1, swap arr[i] and arr[j]

[7, 2, 5, 3, 9]
i = 1, j = 1

Why: 2 is smaller than pivot, keep it on left

Step 4: Lomuto: j=2, 5 <= 9, increment i to 2, swap arr[i] and arr[j]

[7, 2, 5, 3, 9]
i = 2, j = 2

Why: 5 is smaller than pivot, keep it on left

Step 5: Lomuto: j=3, 3 <= 9, increment i to 3, swap arr[i] and arr[j]

[7, 2, 5, 3, 9]
i = 3, j = 3

Why: 3 is smaller than pivot, keep it on left

Step 6: Lomuto: swap pivot arr[i+1] and arr[end], pivot stays at index 4

[7, 2, 5, 3, 9]
Pivot index = 4

Why: Place pivot after all smaller elements

Step 7: Hoare: choose pivot as first element 7, left = low - 1 = -1, right = high + 1 = 5

[7, 2, 5, 3, 9]
left=-1, right=5

Why: Pivot chosen at start, pointers initialized outside the array bounds

Step 8: Hoare: move right leftwards until arr[right] <= pivot: right-- from 5 to 4 (9 > 7), to 3 (3 <= 7)

[7, 2, 5, 3, 9]
left=-1, right=3

Why: Find the first element from right that is <= pivot

Step 9: Hoare: move left rightwards until arr[left] >= pivot: left++ from -1 to 0 (7 >= 7)

[7, 2, 5, 3, 9]
left=0, right=3

Why: Find the first element from left that is >= pivot

Step 10: Hoare: left < right, swap arr[left=0] and arr[right=3]: swap 7 and 3

[3, 2, 5, 7, 9]
left=0, right=3

Why: Swap elements that are on the wrong sides of pivot

Step 11: Hoare: move right leftwards until arr[right] <= pivot: right-- to 2 (5 <= 7)

[3, 2, 5, 7, 9]
left=0, right=2

Why: Continue scanning from right for next <= pivot

Step 12: Hoare: move left rightwards until arr[left] >= pivot: left++ to 1 (2 < 7), to 2 (5 < 7), to 3 (7 >= 7)

[3, 2, 5, 7, 9]
left=3, right=2

Why: Continue scanning from left for next >= pivot

Step 13: Hoare: left >= right, partition ends, return right index 2

[3, 2, 5, 7, 9]
Partition index = 2

Why: Pointers have crossed, partition complete

Result:

Lomuto final: [7, 2, 5, 3, 9], pivot index 4
Hoare final: [3, 2, 5, 7, 9], partition index 2

Annotated Code

DSA Javascript

class QuickSortPartition {
  // Lomuto partition scheme
  static lomutoPartition(arr, low, high) {
    const 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]]; // swap smaller element left
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // place pivot after smaller elements
    return i + 1;
  }

  // Hoare partition scheme
  static hoarePartition(arr, low, high) {
    const pivot = arr[low];
    let left = low - 1;
    let right = high + 1;
    while (true) {
      do {
        right--;
      } while (arr[right] > pivot);
      do {
        left++;
      } while (arr[left] < pivot);
      if (left >= right) return right;
      [arr[left], arr[right]] = [arr[right], arr[left]]; // swap elements on wrong sides
    }
  }
}

// Driver code
const arrLomuto = [7, 2, 5, 3, 9];
const arrHoare = [7, 2, 5, 3, 9];

const lomutoIndex = QuickSortPartition.lomutoPartition(arrLomuto, 0, arrLomuto.length - 1);
const hoareIndex = QuickSortPartition.hoarePartition(arrHoare, 0, arrHoare.length - 1);

console.log('Lomuto partition result:', arrLomuto.join(' -> ') + ' -> null', 'Pivot index:', lomutoIndex);
console.log('Hoare partition result:', arrHoare.join(' -> ') + ' -> null', 'Partition index:', hoareIndex);

const pivot = arr[high];

select pivot as last element for Lomuto

if (arr[j] <= pivot) { i++; swap arr[i] and arr[j]; }

move smaller elements left of pivot

swap arr[i+1] and arr[high]; return i+1;

place pivot after smaller elements

const pivot = arr[low];

select pivot as first element for Hoare

do { right--; } while (arr[right] > pivot);

move right pointer left to find element <= pivot

do { left++; } while (arr[left] < pivot);

move left pointer right to find element >= pivot

if (left >= right) return right;

stop when pointers cross

swap arr[left] and arr[right];

swap elements on wrong sides

Output

Lomuto partition result: 7 -> 2 -> 5 -> 3 -> 9 -> null Pivot index: 4

Hoare partition result: 3 -> 2 -> 5 -> 7 -> 9 -> null Partition index: 2

Complexity Analysis

Time: O(n) because partition scans the array once comparing and swapping elements

Space: O(1) because partition rearranges elements in place without extra storage

vs Alternative: Both Lomuto and Hoare partition run in linear time, but Hoare usually does fewer swaps making it slightly faster in practice

Edge Cases

empty array

partition returns immediately without changes

DSA Javascript

for (let j = low; j < high; j++) { ... } in lomutoPartition prevents loop if empty

array with one element

partition returns pivot index as low or high without swaps

DSA Javascript

for loop in lomutoPartition runs zero times if low == high

all elements equal

Lomuto places pivot at end; Hoare may swap elements but array remains same

DSA Javascript

if (arr[j] <= pivot) condition in Lomuto handles equal elements

When to Use This Pattern

When you need to sort or rearrange an array quickly by dividing it around a pivot, recognize partition schemes like Lomuto or Hoare to efficiently split the array.

Common Mistakes

Mistake: Using wrong pivot index or swapping pivot too early in Lomuto
Fix: Always pick pivot as last element and swap it after scanning all smaller elements

Mistake: In Hoare, not moving pointers correctly causing infinite loop
Fix: Use do-while loops to move pointers at least once before checking conditions

Summary

Partitions an array around a pivot so smaller elements go left and bigger go right.

Use when implementing quicksort to divide and conquer sorting.

The key is how pointers move and swap elements to separate smaller and larger values efficiently.

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