Quick Sort Partition Lomuto and Hoare in DSA Typescript

Mental Model

Partitioning splits an array into parts so elements less than a pivot go left and greater go right, helping quick sort organize data efficiently.

Analogy: Imagine sorting a pile of books by height: pick one book as a reference, then put all shorter books on the left and taller books on the right before sorting each side.

Array: [5, 3, 8, 4, 2]
Pivot chosen -> 2 (Lomuto) or 5 (Hoare)
Indexes:
Lomuto: i and j move through array
Hoare: i from left, j from right

Initial:
[5, 3, 8, 4, 2]
 i,j -> start
Pivot -> last or first element

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Partition the array around a pivot using Lomuto and Hoare methods to prepare for quick sort

Step 1: Lomuto: choose pivot = last element (2), start i at -1, j at 0

[5, 3, 8, 4, 2]
i = -1, j = 0, pivot = 2

Why: Pivot chosen at end; i tracks boundary of smaller elements

Step 2: Lomuto: j=0 (5) > pivot, no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 1

Why: 5 is bigger than pivot, so it stays right

Step 3: Lomuto: j=1 (3) > pivot, no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 2

Why: 3 is bigger than pivot, stays right

Step 4: Lomuto: j=2 (8) > pivot, no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 3

Why: 8 is bigger than pivot, stays right

Step 5: Lomuto: j=3 (4) > pivot, no swap, i stays -1

[5, 3, 8, 4, 2]
i = -1, j = 4

Why: 4 is bigger than pivot, stays right

Step 6: Lomuto: swap pivot (2) with element at i+1 (5)

[2, 3, 8, 4, 5]
i = 0

Why: Place pivot in correct position, all left smaller or equal

Step 7: Hoare: choose pivot = first element (5), i=0, j=4

[5, 3, 8, 4, 2]
i=0, j=4, pivot=5

Why: Pivot chosen at start; i and j move inward

Step 8: Hoare: move j left while arr[j] > pivot: j=4 (2) ≤ 5 stop

[5, 3, 8, 4, 2]
i=0, j=4

Why: Find element smaller or equal to pivot from right

Step 9: Hoare: move i right while arr[i] < pivot: i=0 (5) not < 5 stop

[5, 3, 8, 4, 2]
i=0, j=4

Why: Find element bigger or equal to pivot from left

Step 10: Hoare: swap arr[i] (5) and arr[j] (2), i=1, j=3

[2, 3, 8, 4, 5]
i=1, j=3

Why: Swap to put smaller left and bigger right

Step 11: Hoare: move j left while arr[j] > pivot: j=3 (4) ≤ 5 stop

[2, 3, 8, 4, 5]
i=1, j=3

Why: Find next smaller or equal from right

Step 12: Hoare: move i right while arr[i] < pivot: i=1 (3) < 5 i=2 (8) not < 5 stop

[2, 3, 8, 4, 5]
i=2, j=3

Why: Find next bigger or equal from left

Step 13: Hoare: swap arr[i] (8) and arr[j] (4), i=3, j=2

[2, 3, 4, 8, 5]
i=3, j=2

Why: Swap to correct sides

Step 14: Hoare: i (3) > j (2), partition ends, return j=2

[2, 3, 4, 8, 5]

Why: Pointers crossed, partition done

Result:

Lomuto partitioned array: [2, 3, 8, 4, 5]
Pivot index: 0
Hoare partitioned array: [2, 3, 4, 8, 5]
Partition index: 2

Annotated Code

DSA Typescript

class QuickSortPartition {
  static lomutoPartition(arr: number[], low: number, high: number): number {
    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]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  }

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

// Driver code
const arrLomuto = [5, 3, 8, 4, 2];
const pivotIndexLomuto = QuickSortPartition.lomutoPartition(arrLomuto, 0, arrLomuto.length - 1);
console.log(`Lomuto partitioned array: [${arrLomuto.join(", ")}]`);
console.log(`Pivot index: ${pivotIndexLomuto}`);

const arrHoare = [5, 3, 8, 4, 2];
const pivotIndexHoare = QuickSortPartition.hoarePartition(arrHoare, 0, arrHoare.length - 1);
console.log(`Hoare partitioned array: [${arrHoare.join(", ")}]`);
console.log(`Partition index: ${pivotIndexHoare}`);

const pivot = arr[high];

select pivot as last element for Lomuto

let i = low - 1;

initialize i to track smaller elements boundary

for (let j = low; j < high; j++) {

iterate j through array to compare with pivot

if (arr[j] <= pivot) {

check if current element is smaller or equal to pivot

i++; [arr[i], arr[j]] = [arr[j], arr[i]];

increment i and swap to move smaller element left

[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];

place pivot after last smaller element

const pivot = arr[low];

select pivot as first element for Hoare

let i = low - 1; let j = high + 1;

initialize pointers outside array bounds

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

move j left to find element ≤ pivot

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

move i right to find element ≥ pivot

if (i < j) { swap arr[i] and arr[j]; } else { return j; }

swap elements if pointers not crossed, else return partition index

Output

Lomuto partitioned array: [2, 3, 8, 4, 5]

Pivot index: 0

Hoare partitioned array: [2, 3, 4, 8, 5]

Partition index: 2

Complexity Analysis

Time: O(n) because each partition method scans the array once to rearrange elements around the pivot

Space: O(1) because partitioning is done in place without extra arrays

vs Alternative: Compared to naive methods that create new arrays for less and greater elements, these in-place partitions save space and improve speed

Edge Cases

empty array

partition returns immediately without changes

DSA Typescript

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

array with one element

partition returns the single index as pivot position

DSA Typescript

for loop in lomutoPartition does not run if low == high

all elements equal

partition places pivot correctly but array remains same

DSA Typescript

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

When to Use This Pattern

When you need to sort or organize an array quickly by dividing it around a pivot, recognize the quick sort partition pattern and choose Lomuto or Hoare for efficient in-place partitioning.

Common Mistakes

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

Mistake: In Hoare, moving pointers incorrectly causing infinite loops
Fix: Ensure do-while loops move pointers correctly and stop at proper conditions before swapping

Summary

Partitions an array around a pivot to separate smaller and larger elements for quick sort.

Use when implementing quick sort to efficiently divide and conquer the array.

The key is moving pointers inward and swapping elements to place the pivot correctly without extra space.