Quick Sort Partition Lomuto and Hoare in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Lomuto partition scheme in Quick Sort?

Lomuto partition picks the last element as pivot and rearranges the array so that elements smaller than pivot come before it, and larger come after. It uses one pointer to track the boundary of smaller elements.

intermediate

How does the Hoare partition scheme differ from Lomuto's in Quick Sort?

Hoare partition uses two pointers starting from both ends moving towards each other, swapping elements that are on the wrong side of the pivot. It usually picks the first element as pivot and is more efficient with fewer swaps.

beginner

In Lomuto partition, what happens after the partitioning step?

After partitioning, the pivot is placed in its correct sorted position, with all smaller elements to the left and larger to the right. The array is then recursively sorted on both sides of the pivot.

intermediate

Why is Hoare partition generally faster than Lomuto partition?

Hoare partition does fewer swaps and comparisons on average because it swaps elements only when necessary and stops when pointers cross, making it more efficient especially on large arrays.

intermediate

Show the basic steps of Lomuto partition with an example array [3, 8, 2, 5, 1, 4, 7, 6].

1. Choose pivot = 6 (last element). 2. Start i = -1. 3. Iterate j from 0 to 6: if arr[j] <= pivot, increment i and swap arr[i] and arr[j]. 4. After loop, swap arr[i+1] and pivot. Result: [3, 2, 1, 5, 4, 6, 7, 8] with pivot at index 5.

In Lomuto partition, which element is usually chosen as the pivot?

A Middle element

B First element

C Random element

D Last element

Lomuto partition typically chooses the last element as the pivot.

What is the stopping condition for the pointers in Hoare partition?

A When all elements are sorted

B When pointers meet at the pivot

C When pointers cross each other

D After one full pass through the array

In Hoare partition, the process stops when the two pointers cross each other.

Which partition scheme generally uses fewer swaps?

A Hoare

B Lomuto

C Both use the same number

D Depends on the array size

Hoare partition usually uses fewer swaps than Lomuto.

After Lomuto partition, where is the pivot placed?

A At its correct sorted position

B At the start of the array

C At the end of the array

D Pivot position does not change

Lomuto partition places the pivot at its correct sorted position.

Which partition scheme is more suitable for arrays with many duplicate elements?

A Lomuto

B Hoare

C Both are equally suitable

D Neither is suitable

Hoare partition handles duplicates more efficiently by reducing unnecessary swaps.

Explain step-by-step how Lomuto partition rearranges an array around a pivot.

Think about how the pointer moves and swaps during iteration.

Describe how Hoare partition uses two pointers to partition an array and why it can be more efficient.

Visualize two people walking towards each other swapping misplaced items.

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