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 a single index to track the boundary between smaller and larger elements.
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 that are on the wrong side of the pivot. It usually picks the first element as pivot and can be more efficient with fewer swaps.
Click to reveal answer
beginner
In Lomuto partition, what happens after the partitioning is done?
The pivot element is placed in its correct sorted position, with all smaller elements to its left and larger to its right. This divides the array into two parts for recursive sorting.
Click to reveal answer
intermediate
Why might Hoare partition be preferred over Lomuto partition in some cases?
Hoare partition often performs fewer swaps and can be faster because it stops when the two indices cross, not necessarily placing the pivot at the exact final position immediately.
Click to reveal answer
advanced
Show the basic Go code snippet for Lomuto partition function.
func lomutoPartition(arr []int, low, high int) int {
pivot := arr[high]
i := low
for 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
}
Click to reveal answer
Which element is typically chosen as pivot in Lomuto partition?
✗ Incorrect
Lomuto partition usually picks the last element as the pivot.
In Hoare partition, what happens when the two indices cross?
✗ Incorrect
Partitioning ends when the two indices cross in Hoare partition.
Which partition scheme generally uses fewer swaps?
✗ Incorrect
Hoare partition usually performs fewer swaps than Lomuto.
What is the main purpose of partitioning in Quick Sort?
✗ Incorrect
Partitioning divides the array around the pivot to recursively sort subarrays.
In Lomuto partition, what does the index 'i' represent?
✗ Incorrect
'i' tracks the boundary between elements smaller than pivot and others.
Explain how Lomuto partition rearranges the array around the pivot.
Think about how the last element is used and how smaller elements are moved.
You got /4 concepts.
Describe the steps of Hoare partition and why it might be more efficient.
Focus on the movement of two pointers and when partitioning stops.
You got /4 concepts.