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.

Practice

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

easy

A. Lomuto uses a single 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 always picks the first element as pivot, Hoare picks the last

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses one 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 around the pivot.

3. Final Answer:

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

4. Quick Check:

   Pointer count difference = A [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking both use the same pointer approach
• Assuming sorting order differs

2. Which of the following is the correct TypeScript function signature for Lomuto partition?

easy

A. function lomutoPartition(arr: number[]): number[]

B. function lomutoPartition(arr: number[], start: number): void

C. function lomutoPartition(arr: number[], low: number, high: number): number

D. function lomutoPartition(arr: number[], low: number, high: number): void

Solution

1. Step 1: Check parameters needed

   Lomuto partition requires the array and two indices: low and high to define the segment.

2. Step 2: Check return type

   It returns the pivot index after partitioning, so return type is number.

3. Final Answer:

   function lomutoPartition(arr: number[], low: number, high: number): number -> Option C

4. Quick Check:

   Parameters and return match = C [OK]

Hint: Lomuto returns pivot index, needs low and high indices [OK]

Common Mistakes:

• Missing high index parameter
• Wrong return type (void instead of number)
• Using only array parameter

3. What is the output array after applying Lomuto partition on [8, 3, 7, 6, 2] with low=0 and high=4?

medium

A. [2, 3, 7, 6, 8]

B. [3, 2, 7, 6, 8]

C. [2, 3, 6, 7, 8]

D. [8, 3, 7, 6, 2]

Solution

1. Step 1: Choose 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 8 and 2.

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start = A [OK]

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

Common Mistakes:

• Not swapping pivot correctly
• Swapping elements greater than pivot
• Confusing pointer i initialization

4. Identify the bug in this Hoare partition code snippet:

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

medium

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

B. Pointers i and j can go out of bounds causing error

C. Return statement should be i not j

D. Swapping should happen before pointer checks

Solution

1. Step 1: Analyze pointer increments

   i increments while arr[i] < pivot but no boundary check; similarly j decrements without boundary check.

2. Step 2: Identify risk of out-of-bounds

   If all elements are less or greater than pivot, i or j can move beyond array limits causing runtime error.

3. Final Answer:

   Pointers i and j can go out of bounds causing error -> Option B

4. Quick Check:

   Missing boundary checks = B [OK]

Hint: Always check array bounds when moving pointers [OK]

Common Mistakes:

• Ignoring pointer boundary conditions
• Changing pivot position unnecessarily
• Returning wrong pointer index

5. Given the array [10, 80, 30, 90, 40, 50, 70], what is the final array after one full Hoare partition call with low=0 and high=6?

hard

A. [10, 30, 40, 50, 70, 90, 80]

B. [10, 30, 40, 50, 90, 70, 80]

C. [10, 30, 40, 50, 80, 70, 90]

D. [10, 80, 30, 90, 40, 50, 70]

Solution

1. Step 1: Set pivot and pointers

   Pivot = arr[low] = 10. i = low + 1 = 1, j = high = 6.

2. Step 2: Move i pointer

   while (arr[i] < 10) i++; arr[1]=80 not < 10, i remains 1.

3. Step 3: Move j pointer

   while (arr[j] > 10) j--; From j=6 (70>10) to 5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), so j=0.

4. Step 4: Check crossing and swaps

   i=1 >= j=0, return j. No swaps performed. Array unchanged.

5. Step 5: Correction - Hoare partition typically swaps elements before pointers cross

   Actually, the pointers cross immediately because pivot is smallest element, so no swaps occur and array remains unchanged.

6. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option D

7. Quick Check:

   Pivot smallest, pointers cross without swaps = A [OK]

Hint: Trace pointers inward carefully for Hoare partition [OK]

Common Mistakes:

• Stopping j pointer movement too early
• Assuming the partition fully sorts subarrays
• Mixing Lomuto and Hoare swap logic