Challenge - 5 Problems
Quick Sort Partition Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Lomuto Partition on a sample array
What is the output of the Lomuto partition function on the array after partitioning?
DSA Rust
fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[high];
let mut i = low;
for j in low..high {
if arr[j] < pivot {
arr.swap(i, j);
i += 1;
}
}
arr.swap(i, high);
i
}
fn main() {
let mut arr = [9, 3, 7, 6, 2, 8, 5];
let p = lomuto_partition(&mut arr, 0, arr.len() - 1);
println!("Partition index: {}", p);
println!("Array after partition: {:?}", arr);
}Attempts:
2 left
💡 Hint
Remember Lomuto uses the last element as pivot and places smaller elements before it.
✗ Incorrect
The Lomuto partition picks the last element (5) as pivot. It moves all elements smaller than 5 to the left. The pivot ends up at index 2 after swaps. The array is rearranged accordingly.
❓ Predict Output
intermediate2:00remaining
Output of Hoare Partition on a sample array
What is the output of the Hoare partition function on the array after partitioning?
DSA Rust
fn hoare_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[low];
let mut i = low as isize - 1;
let mut j = high as isize + 1;
loop {
loop {
i += 1;
if arr[i as usize] >= pivot {
break;
}
}
loop {
j -= 1;
if arr[j as usize] <= pivot {
break;
}
}
if i >= j {
return j as usize;
}
arr.swap(i as usize, j as usize);
}
}
fn main() {
let mut arr = [8, 3, 7, 6, 2, 5, 4];
let p = hoare_partition(&mut arr, 0, arr.len() - 1);
println!("Partition index: {}", p);
println!("Array after partition: {:?}", arr);
}Attempts:
2 left
💡 Hint
Hoare partition uses the first element as pivot and swaps elements crossing from left and right.
✗ Incorrect
Hoare partition picks the first element (8) as pivot. It moves indices inward swapping elements to ensure left side smaller or equal, right side larger or equal. The partition index is 5, and array is rearranged accordingly.
🧠 Conceptual
advanced1:30remaining
Difference between Lomuto and Hoare partition schemes
Which statement correctly describes a key difference between Lomuto and Hoare partition schemes?
Attempts:
2 left
💡 Hint
Think about where the pivot ends up after partitioning.
✗ Incorrect
Lomuto partition places the pivot at its correct sorted position after partitioning. Hoare partition returns an index but does not guarantee the pivot is at its final position.
🔧 Debug
advanced2:00remaining
Identify the error in this Lomuto partition implementation
What error will this Lomuto partition code cause when run?
DSA Rust
fn lomuto_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[high];
let mut i = low - 1;
for j in low..high {
if arr[j] < pivot {
i += 1;
arr.swap(i, j);
}
}
arr.swap(i + 1, high);
i + 1
}
fn main() {
let mut arr = [4, 5, 3, 7, 2];
let p = lomuto_partition(&mut arr, 0, arr.len() - 1);
println!("Partition index: {}", p);
println!("Array after partition: {:?}", arr);
}Attempts:
2 left
💡 Hint
Check the initialization of variable i when low is zero.
✗ Incorrect
In Rust, subtracting 1 from zero for unsigned integers causes underflow and panic. The line 'let mut i = low - 1;' is unsafe when low is 0.
🚀 Application
expert3:00remaining
Resulting array after full quicksort using Hoare partition
Given the array [10, 7, 8, 9, 1, 5], what is the final sorted array after applying quicksort with Hoare partition scheme?
DSA Rust
fn hoare_partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[low];
let mut i = low as isize - 1;
let mut j = high as isize + 1;
loop {
loop {
i += 1;
if arr[i as usize] >= pivot {
break;
}
}
loop {
j -= 1;
if arr[j as usize] <= pivot {
break;
}
}
if i >= j {
return j as usize;
}
arr.swap(i as usize, j as usize);
}
}
fn quicksort(arr: &mut [i32], low: usize, high: usize) {
if low < high {
let p = hoare_partition(arr, low, high);
if p > 0 {
quicksort(arr, low, p);
}
quicksort(arr, p + 1, high);
}
}
fn main() {
let mut arr = [10, 7, 8, 9, 1, 5];
let len = arr.len();
quicksort(&mut arr, 0, len - 1);
println!("Sorted array: {:?}", arr);
}Attempts:
2 left
💡 Hint
Hoare partition quicksort sorts the array in ascending order.
✗ Incorrect
The quicksort implementation using Hoare partition correctly sorts the array in ascending order: [1, 5, 7, 8, 9, 10].