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.