Quick Sort Partition Lomuto and Hoare in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on Array

What is the output array after applying Lomuto partition on the array [8, 3, 7, 6, 2] with pivot as last element?

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 arr;
}

const arr = [8, 3, 7, 6, 2];
lomutoPartition(arr, 0, arr.length - 1);
console.log(arr);

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

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

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

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

💡 Hint

Remember Lomuto places pivot at its correct position and partitions smaller elements to left.

Lomuto partition picks last element as pivot (2). It moves all elements <= 2 to left. Only 2 is <= 2, so it swaps 2 with first element. Result: [2, 3, 7, 6, 8]

❓ Predict Output

intermediate

Output of Hoare Partition on Array

What is the output array after applying Hoare partition on the array [5, 1, 4, 2, 8] with pivot as first element?

DSA Javascript

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 arr;
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
}

const arr = [5, 1, 4, 2, 8];
hoarePartition(arr, 0, arr.length - 1);
console.log(arr);

A [5, 1, 4, 2, 8]

B [2, 1, 4, 5, 8]

C [1, 2, 4, 5, 8]

D [4, 1, 2, 5, 8]

💡 Hint

Hoare partition swaps elements around pivot until pointers cross.

Pivot is 5. Hoare moves i right until >=5 and j left until <=5, swapping elements. After swaps, array becomes [4, 1, 2, 5, 8].

🧠 Conceptual

advanced

Difference Between Lomuto and Hoare Partition

Which statement correctly describes a key difference between Lomuto and Hoare partition schemes?

A Lomuto partition places pivot at its final position after partition, Hoare may not.

B Hoare partition always places pivot at its final sorted position, Lomuto does not.

C Lomuto partition uses two pointers moving inward, Hoare uses one pointer moving forward.

D Hoare partition uses the last element as pivot, Lomuto uses the first element.

💡 Hint

Think about where the pivot ends after partition in each scheme.

Lomuto places pivot at its correct sorted position after partition. Hoare partition rearranges elements but pivot may not be at final position.

🔧 Debug

advanced

Identify the Bug in Lomuto Partition Code

What error will this Lomuto partition code produce when run on array [4, 9, 3, 7]? function lomutoPartition(arr, low, high) { let pivot = arr[high]; let i = low; for (let j = low; j < high; j++) { if (arr[j] <= pivot) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; } } [arr[i], arr[high]] = [arr[high], arr[i]]; return i; }

A No error; returns correct pivot index

B TypeError due to invalid swap syntax

C Off-by-one error causing incorrect pivot placement

D Infinite loop due to wrong loop condition

💡 Hint

Check initial value of i and how it affects swaps.

Initial i should be low - 1, not low. Starting at low causes pivot to be misplaced, off-by-one error.

🚀 Application

expert

Number of Items Left of Pivot After Hoare Partition

Given array [10, 7, 8, 9, 1, 5] and pivot as first element (10), after applying Hoare partition, how many elements are guaranteed to be on the left side of the pivot's final position?

A All elements except pivot are on left

B At least one element less than or equal to pivot is on left

C No elements are guaranteed on left side

D Exactly half of the elements are on left side

💡 Hint

Hoare partition rearranges but pivot may not be at final position.

Hoare partition ensures elements less than or equal to pivot are on one side, but pivot's final position is not fixed. So at least one element <= pivot is on left.