Quick Sort as Divide and Conquer 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 after running on the array [4, 2, 7, 1, 3] with pivot as the last element?

DSA Rust

fn partition(arr: &mut [i32]) -> usize {
    let pivot = arr[arr.len() - 1];
    let mut i = 0;
    for j in 0..arr.len() - 1 {
        if arr[j] < pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, arr.len() - 1);
    i
}

fn main() {
    let mut arr = [4, 2, 7, 1, 3];
    let p = partition(&mut arr);
    println!("Partition index: {}", p);
    println!("Array after partition: {:?}", arr);
}

A

Partition index: 2
Array after partition: [2, 1, 4, 3, 7]

B

Partition index: 3
Array after partition: [2, 1, 3, 4, 7]

C

Partition index: 4
Array after partition: [1, 2, 3, 4, 7]

D

Partition index: 1
Array after partition: [1, 4, 2, 3, 7]

💡 Hint

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

The pivot is 3. Elements less than 3 are 2 and 1, which are moved to the left. The pivot is placed at index 2 after swapping. The array becomes [2, 1, 3, 4, 7].

🧠 Conceptual

intermediate

Understanding Quick Sort's Divide and Conquer

Which statement best describes the divide and conquer approach in Quick Sort?

A Quick Sort divides the array into two parts around a pivot and recursively sorts each part.

B Quick Sort merges two sorted arrays into one sorted array.

C Quick Sort uses a heap to repeatedly extract the smallest element.

D Quick Sort sorts the array by repeatedly swapping adjacent elements.

💡 Hint

Think about how Quick Sort breaks down the problem into smaller parts.

Quick Sort picks a pivot, partitions the array into elements less than and greater than the pivot, then recursively sorts these parts.

🔧 Debug

advanced

Identify the Bug in Quick Sort Implementation

What error will this Rust Quick Sort code produce when sorting [3, 1, 4]? fn quick_sort(arr: &mut [i32]) { if arr.len() <= 1 { return; } let pivot_index = arr.len() / 2; let pivot = arr[pivot_index]; let mut left = 0; let mut right = arr.len() - 1; while left <= right { while arr[left] < pivot { left += 1; } while arr[right] > pivot { right -= 1; } if left <= right { arr.swap(left, right); left += 1; right -= 1; } } quick_sort(&mut arr[0..right]); quick_sort(&mut arr[left..arr.len()]); }

A panic: index out of bounds at arr[0..right] when right is usize::MAX

B Stack overflow due to infinite recursion

C Compilation error due to mutable borrow conflict

D No error, sorts correctly

💡 Hint

Check what happens when right becomes negative and is used as usize index.

When right becomes -1 and is cast to usize, it becomes a very large number causing out of bounds slicing panic.

📝 Syntax

advanced

Correct Rust Syntax for Recursive Quick Sort Call

Which option correctly calls quick_sort recursively on the left partition of the array slice arr[0..pivot_index] in Rust?

A quick_sort(arr[0..pivot_index]);

B quick_sort(&mut arr[0:pivot_index]);

C quick_sort(&arr[0..pivot_index]);

D quick_sort(&mut arr[0..pivot_index]);

💡 Hint

Remember Rust slice syntax and mutable references.

Rust slices use .. for ranges and &mut for mutable references. Option D uses both correctly.

🚀 Application

expert

Final Sorted Array After Full Quick Sort

Given the Rust quick_sort function below, what is the final sorted array after calling quick_sort on [5, 3, 8, 4, 2]? fn quick_sort(arr: &mut [i32]) { if arr.len() <= 1 { return; } let pivot_index = arr.len() / 2; let pivot = arr[pivot_index]; let mut left = 0; let mut right = arr.len() - 1; while left <= right { while arr[left] < pivot { left += 1; } while arr[right] > pivot { right -= 1; } if left <= right { arr.swap(left, right); left += 1; right -= 1; } } quick_sort(&mut arr[0..=right]); quick_sort(&mut arr[left..arr.len()]); }

A [3, 2, 4, 5, 8]

B [2, 3, 5, 4, 8]

C [2, 3, 4, 5, 8]

D [5, 3, 8, 4, 2]

💡 Hint

Trace the partitioning and recursive calls carefully.

The function correctly partitions and recursively sorts both sides, resulting in a fully sorted array [2, 3, 4, 5, 8].

Practice

1. What is the main idea behind the Quick Sort algorithm as a divide and conquer method?

easy

A. Sort the list by selecting the largest element first

B. Sort the list by repeatedly swapping adjacent elements

C. Use extra memory to merge sorted lists

D. Divide the list into smaller parts, sort them, then combine

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the list into smaller parts based on a pivot, sorts each part, then combines results.

2. Step 2: Compare options with this idea

   Divide the list into smaller parts, sort them, then combine matches this process exactly, others describe different sorting methods.

3. Final Answer:

   Divide the list into smaller parts, sort them, then combine -> Option D

4. Quick Check:

   Divide and conquer = Divide, sort, combine [OK]

Hint: Remember Quick Sort splits and sorts parts separately [OK]

Common Mistakes:

• Confusing Quick Sort with Bubble Sort
• Thinking Quick Sort merges sorted lists like Merge Sort
• Assuming Quick Sort sorts by largest element first

2. Which of the following Rust function signatures correctly represents a Quick Sort function that sorts a mutable slice of integers?

easy

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

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

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

D. fn quick_sort(arr: &mut Vec<i32>) -> 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 return type and parameter correctness

   fn quick_sort(arr: &mut [i32]) matches this: it takes &mut [i32] and returns nothing (unit). Others either take immutable slices or return new vectors.

3. Final Answer:

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

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 when mutation is needed
• Returning a new vector unnecessarily
• Returning wrong type like i32

3. What will be the output of the following Rust code snippet using Quick Sort?

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 if arr[right] > pivot {
            right -= 1;
        } else {
            arr.swap(left, right);
            left += 1;
            right -= 1;
        }
    }
    arr.swap(0, right);
    quick_sort(&mut arr[0..right]);
    quick_sort(&mut arr[right+1..]);
}

fn main() {
    let mut data = [3, 6, 2, 7, 5];
    quick_sort(&mut data);
    println!("{:?}", data);
}

medium

A. [2, 3, 5, 6, 7]

B. [3, 2, 6, 5, 7]

C. [7, 6, 5, 3, 2]

D. [2, 3, 6, 5, 7]

Solution

1. Step 1: Trace partitioning with pivot 3

   Pivot is 3. Elements <=3 go left, >3 go right. After partition, array becomes [2, 3, 5, 7, 6] with pivot at index 1.

2. Step 2: Recursively sort left and right parts

   Left part [2] is sorted (single element). Right part [5,7,6] sorts to [5,6,7]. Final sorted array is [2, 3, 5, 6, 7].

3. Final Answer:

   [2, 3, 5, 6, 7] -> Option A

4. Quick Check:

   Sorted array = [2, 3, 5, 6, 7] [OK]

Hint: Pivot divides array; recursively sort left and right [OK]

Common Mistakes:

• Not swapping pivot correctly
• Confusing left and right pointers
• Missing recursive calls on subarrays

4. Identify the bug in this Quick Sort Rust code snippet and choose the correct fix:

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

medium

A. Initialize left to 1 instead of 0

B. Change while condition to left <= right

C. Swap pivot with arr[left] instead of arr[right]

D. Remove the inner while loops

Solution

1. Step 1: Analyze left pointer initialization

   Left starts at 0, same as pivot index, causing infinite loop because arr[left] <= pivot is always true initially.

2. Step 2: Fix by starting left at 1

   Starting left at 1 avoids comparing pivot with itself and allows pointers to move correctly.

3. Final Answer:

   Initialize left to 1 instead of 0 -> Option A

4. Quick Check:

   Left pointer start = 1 fixes infinite loop [OK]

Hint: Start left pointer after pivot to avoid infinite loop [OK]

Common Mistakes:

• Leaving left at 0 causing no progress
• Changing conditions without fixing pointer start
• Swapping with wrong index causing wrong partition

5. Given a list of integers with many duplicate values, how can you modify the Quick Sort algorithm in Rust to improve performance and avoid worst-case behavior?

hard

A. Sort the list twice to ensure duplicates are handled

B. Use a three-way partitioning to separate less, equal, and greater elements

C. Always choose the first element as pivot without changes

D. Remove duplicates before sorting

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Duplicates cause unbalanced partitions leading to worst-case O(n²) time if pivot is always chosen poorly.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into elements less than, equal to, and greater than pivot, handling duplicates efficiently and improving performance.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option B

4. Quick Check:

   Three-way partitioning handles duplicates well [OK]

Hint: Use three-way partitioning for duplicates to speed up sorting [OK]

Common Mistakes:

• Ignoring duplicates causing slow sorting
• Choosing fixed pivot without randomization or partitioning
• Removing duplicates changes data, not always allowed