Quick Sort Algorithm in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Quick Sort Partition Step

What is the output of the partition function on the array after the first partition call?

DSA Rust

fn 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 = [10, 7, 8, 9, 1, 5];
    let p = partition(&mut arr, 0, arr.len() - 1);
    println!("{:?}", arr);
    println!("Partition index: {}", p);
}

A [1, 7, 8, 9, 5, 10]\nPartition index: 4

B [1, 7, 8, 9, 10, 5]\nPartition index: 1

C [1, 5, 8, 9, 7, 10]\nPartition index: 1

D [1, 5, 7, 8, 9, 10]\nPartition index: 5

💡 Hint

Remember the pivot is the last element and elements less than pivot are moved to the left.

The partition function uses the last element as pivot (5). It moves all elements less than 5 to the left. After partition, the array becomes [1, 5, 8, 9, 7, 10] and pivot index is 1.

❓ Predict Output

intermediate

Final Sorted Array from Quick Sort

What is the output of the array after the full quick sort completes?

DSA Rust

fn quick_sort(arr: &mut [i32], low: isize, high: isize) {
    if low < high {
        let p = partition(arr, low as usize, high as usize);
        quick_sort(arr, low, p as isize - 1);
        quick_sort(arr, p as isize + 1, high);
    }
}

fn 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 = [10, 7, 8, 9, 1, 5];
    let len = arr.len();
    quick_sort(&mut arr, 0, (len - 1) as isize);
    println!("{:?}", arr);
}

A [10, 9, 8, 7, 5, 1]

B [1, 5, 7, 8, 9, 10]

C [5, 1, 7, 8, 9, 10]

D [1, 7, 5, 8, 9, 10]

💡 Hint

Quick sort sorts the array in ascending order.

Quick sort recursively partitions and sorts the array. The final sorted array is [1, 5, 7, 8, 9, 10].

🔧 Debug

advanced

Identify the Bug in Quick Sort Recursive Call

What error will this quick sort code produce when run?

DSA Rust

fn quick_sort(arr: &mut [i32], low: usize, high: usize) {
    if low < high {
        let p = partition(arr, low, high);
        quick_sort(arr, low, p - 1);
        quick_sort(arr, p + 1, high);
    }
}

fn 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 = [3, 6, 8, 10, 1, 2, 1];
    quick_sort(&mut arr, 0, arr.len() - 1);
    println!("{:?}", arr);
}

A Panic due to unsigned integer underflow when p is 0 and p - 1 is computed

B Stack overflow due to infinite recursion

C Compilation error due to type mismatch

D Runs correctly and prints sorted array

💡 Hint

Check what happens when p equals low (0) and you subtract 1 from it.

Since low and high are usize (unsigned), p - 1 when p is 0 causes underflow panic at runtime.

🧠 Conceptual

advanced

Time Complexity of Quick Sort in Worst Case

What is the worst-case time complexity of quick sort and when does it occur?

A O(n), occurs when array is already sorted

B O(n log n), occurs when pivot divides array into two equal halves

C O(log n), occurs when pivot is chosen randomly

D O(n^2), occurs when pivot is always the smallest or largest element

💡 Hint

Think about how unbalanced partitions affect recursion depth.

Worst case O(n^2) happens when pivot is smallest or largest element repeatedly, causing unbalanced partitions.

🚀 Application

expert

Quick Sort Partition Index for Duplicate Elements

Given the array [4, 5, 4, 3, 4, 2, 4] and using the last element as pivot, what is the partition index after the first partition call?

DSA Rust

fn 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 = [4, 5, 4, 3, 4, 2, 4];
    let p = partition(&mut arr, 0, arr.len() - 1);
    println!("Partition index: {}", p);
    println!("Array after partition: {:?}", arr);
}

A Partition index: 4\nArray after partition: [3, 2, 4, 4, 4, 5, 4]

B Partition index: 3\nArray after partition: [3, 2, 4, 4, 5, 4, 4]

C Partition index: 5\nArray after partition: [3, 2, 4, 4, 5, 4, 4]

D Partition index: 2\nArray after partition: [3, 2, 4, 5, 4, 4, 4]

💡 Hint

Elements equal to pivot are not moved before pivot index.

Only elements less than pivot (4) move left. Elements equal to pivot stay after. Partition index is 4 after swaps.

Practice

1. What is the main idea behind the Quick Sort algorithm?

easy

A. Merge two sorted lists into one sorted list

B. Compare every element with every other element and swap if needed

C. Sort the list by repeatedly finding the minimum element

D. Divide the list into smaller parts using a pivot and sort them recursively

Solution

1. Step 1: Understand Quick Sort's approach

   Quick Sort picks a pivot element and divides the list into parts smaller and larger than the pivot.

2. Step 2: Recursive sorting of parts

   It then sorts these parts recursively, combining them to get the sorted list.

3. Final Answer:

   Divide the list into smaller parts using a pivot and sort them recursively -> Option D

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: pivot divides list, then sort parts recursively [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges lists like Merge Sort
• Believing Quick Sort always picks the first element as pivot

2. Which of the following is the correct Rust function signature for a Quick Sort function that sorts a mutable slice of integers?

easy

A. fn quick_sort(arr: &mut [i32])

B. fn quick_sort(arr: Vec<i32>) -> Vec<i32>

C. fn quick_sort(arr: &[i32]) -> &[i32]

D. fn quick_sort(arr: &mut Vec<i32>) -> ()

Solution

1. Step 1: Identify correct parameter type for in-place sorting

   Quick Sort usually sorts in place, so it needs a mutable slice reference: &mut [i32].

2. Step 2: Check function signature correctness

   fn quick_sort(arr: &mut [i32]) matches this: it takes &mut [i32] and returns nothing (unit type implied).

3. Final Answer:

   fn quick_sort(arr: &mut [i32]) -> Option A

4. Quick Check:

   Mutable slice parameter = fn quick_sort(arr: &mut [i32]) [OK]

Hint: Quick Sort sorts in place, so use &mut slice parameter [OK]

Common Mistakes:

• Using immutable slice &[] which cannot be changed
• Returning a new vector instead of sorting in place
• Using Vec<i32> without mutability for in-place sort

3. What will be the output of the following Rust code snippet after calling quick_sort(&mut arr)?

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 { return; }
    let pivot = arr[0];
    let mut left = 1;
    let mut right = arr.len() - 1;
    while left <= right {
        if arr[left] <= pivot {
            left += 1;
        } else {
            arr.swap(left, right);
            if right == 0 { break; }
            right -= 1;
        }
    }
    arr.swap(0, right);
    quick_sort(&mut arr[0..right]);
    quick_sort(&mut arr[right+1..]);
}

fn main() {
    let mut arr = [4, 2, 7, 1, 3];
    quick_sort(&mut arr);
    println!("{:?}", arr);
}

medium

A. [1, 2, 3, 7, 4]

B. [1, 2, 3, 4, 7]

C. [4, 2, 7, 1, 3]

D. [7, 4, 3, 2, 1]

Solution

1. Step 1: Understand partitioning around pivot

   The pivot is 4. Elements <=4 move left, >4 move right. After partition, array becomes [3, 2, 1, 4, 7] with pivot at index 3.

2. Step 2: Recursive calls sort left and right parts

   Left part [3, 2, 1] sorts to [1, 2, 3], right part [7] is already sorted. Combined final array is [1, 2, 3, 4, 7].

3. Final Answer:

   [1, 2, 3, 4, 7] -> Option B

4. Quick Check:

   Sorted array = [1, 2, 3, 4, 7] [OK]

Hint: Trace pivot swaps and recursive calls carefully [OK]

Common Mistakes:

• Ignoring pivot swaps and recursive sorting
• Assuming array remains unchanged
• Mixing up left and right partitions

4. Identify the bug in this Rust Quick Sort implementation:

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 { return; }
    let pivot = arr[0];
    let mut left = 1;
    let mut right = arr.len() - 1;
    while left < right {
        if arr[left] <= pivot {
            left += 1;
        } else {
            arr.swap(left, right);
            right -= 1;
        }
    }
    arr.swap(0, right);
    quick_sort(&mut arr[0..right]);
    quick_sort(&mut arr[right+1..]);
}

medium

A. The while loop condition should be <= instead of <

B. Pivot should be chosen as the last element, not the first

C. The recursive calls should use inclusive ranges

D. The swap after the loop should be with left, not right

Solution

1. Step 1: Analyze the while loop condition

   The loop uses while left < right, but it must include the case when left == right to correctly partition.

2. Step 2: Effect of incorrect loop condition

   Stopping early misses some comparisons, causing incorrect partition and sorting errors.

3. Final Answer:

   The while loop condition should be <= instead of < -> Option A

4. Quick Check:

   Loop condition must cover all indices [OK]

Hint: Check loop boundaries carefully in partition step [OK]

Common Mistakes:

• Ignoring edge case when left equals right
• Changing pivot choice unnecessarily
• Misusing slice ranges in recursive calls

5. You want to sort a large list of integers using Quick Sort in Rust. Which strategy helps avoid worst-case performance when the input is already sorted or nearly sorted?

hard

A. Always pick the first element as pivot

B. Use Bubble Sort instead for sorted inputs

C. Pick a random element as pivot each time

D. Sort only the first half of the list

Solution

1. Step 1: Understand worst-case in Quick Sort

   Picking the first element as pivot on sorted input causes unbalanced partitions, leading to worst-case O(n²) time.

2. Step 2: Use random pivot to avoid worst-case

   Choosing a random pivot spreads partitions more evenly, improving average performance and avoiding worst-case.

3. Final Answer:

   Pick a random element as pivot each time -> Option C

4. Quick Check:

   Random pivot = better average case [OK]

Hint: Randomize pivot to prevent worst-case input issues [OK]

Common Mistakes:

• Always picking first element as pivot
• Switching to Bubble Sort unnecessarily
• Sorting only part of the list