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.

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