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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
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.
Click to reveal answer
In Lomuto partition, which element is usually chosen as the pivot?
✗ Incorrect
Lomuto partition typically chooses the last element as the pivot.
What is the stopping condition for the pointers in Hoare partition?
✗ Incorrect
In Hoare partition, the process stops when the two pointers cross each other.
Which partition scheme generally uses fewer swaps?
✗ Incorrect
Hoare partition usually uses fewer swaps than Lomuto.
After Lomuto partition, where is the pivot placed?
✗ Incorrect
Lomuto partition places the pivot at its correct sorted position.
Which partition scheme is more suitable for arrays with many duplicate elements?
✗ Incorrect
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.
You got /4 concepts.
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.
You got /5 concepts.