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 or equal to pivot come before it, and larger come after. It returns the pivot's final position.
Click to reveal answer
intermediate
How does the Hoare partition scheme differ from Lomuto's in Quick Sort?
Hoare partition uses two indices starting from both ends moving towards each other, swapping elements to ensure left side is smaller and right side is larger than pivot. It returns an index near the pivot but not necessarily its final position.
Click to reveal answer
beginner
Show the Lomuto partition pseudocode steps.
1. Choose last element as pivot.
2. Initialize i to low-1.
3. For each element j from low to high-1:
- If arr[j] <= pivot, increment i and swap arr[i] and arr[j].
4. Swap arr[i+1] and pivot.
5. Return i+1 as pivot index.
Click to reveal answer
intermediate
What is a key advantage of Hoare partition over Lomuto partition?
Hoare partition generally performs fewer swaps and can be more efficient, especially on large arrays, because it partitions in place with two pointers and stops earlier.
Click to reveal answer
beginner
What is the output of Lomuto partition on array [3, 8, 2, 5, 1, 4, 7, 6]?
After partitioning with pivot=6 (last element), array becomes [3, 2, 5, 1, 4, 6, 7, 8] and pivot index returned is 5.
Click to reveal answer
In Lomuto partition, which element is chosen as the pivot?
✗ Incorrect
Lomuto partition always picks the last element as the pivot.
What does Hoare partition return after partitioning?
✗ Incorrect
Hoare partition returns an index near the pivot but not necessarily the pivot's final position.
Which partition scheme generally uses fewer swaps?
✗ Incorrect
Hoare partition usually performs fewer swaps than Lomuto.
In Lomuto partition, what happens when an element is less than or equal to the pivot?
✗ Incorrect
Elements less than or equal to pivot are swapped to the left side.
Which partition scheme uses two pointers moving inward from both ends?
✗ Incorrect
Hoare partition uses two pointers starting from both ends moving inward.
Explain step-by-step how Lomuto partition rearranges an array.
Think about how elements smaller than pivot are moved left.
You got /5 concepts.
Describe the differences between Lomuto and Hoare partition schemes and when you might prefer one over the other.
Consider how pointers move and what index is returned.
You got /5 concepts.