Quick Sort as Divide and Conquer in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Rust

fn swap(arr: &mut [i32], i: usize, j: usize) {
    let temp = arr[[1]];
    arr[i] = arr[j];
    arr[j] = temp;
}

Drag options to blanks, or click blank then click option'

A1

Bi

C0

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index for temp causes incorrect swapping.

Swapping without a temporary variable leads to data loss.

We store the element at index i in temp before swapping.

2fill in blank

medium

Complete the code to choose the pivot element as the last element of the array slice.

DSA Rust

fn partition(arr: &mut [i32]) -> usize {
    let pivot = arr[[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
}

Drag options to blanks, or click blank then click option'

Aarr.len() - 1

B1

Carr.len()

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using arr.len() causes out-of-bounds error.

Choosing the first element instead of the last changes pivot behavior.

The pivot is chosen as the last element, so its index is arr.len() - 1.

3fill in blank

hard

Fix the error in the recursive quicksort call to sort the left partition correctly.

DSA Rust

fn quicksort(arr: &mut [i32]) {
    if arr.len() > 1 {
        let pivot_index = partition(arr);
        quicksort(&mut arr[0..[1]]);
        quicksort(&mut arr[pivot_index + 1..arr.len()]);
    }
}

Drag options to blanks, or click blank then click option'

Aarr.len()

Bpivot_index + 1

Cpivot_index

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using pivot_index + 1 skips the pivot and misses elements.

Using arr.len() sorts the whole array again causing infinite recursion.

The left partition is from start to pivot_index (exclusive), so use 0..pivot_index.

4fill in blank

hard

Fill both blanks to correctly partition the array and return the pivot index.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Aarr.len() - 1

B<=

C<

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using < excludes elements equal to pivot causing unstable sort.

Using 0 as pivot index causes wrong pivot selection.

The pivot is the last element, so index is arr.len() - 1. We compare elements less than or equal to pivot using <=.

5fill in blank

hard

Fill all three blanks to complete the quicksort function with correct recursive calls and base case.

DSA Rust

fn quicksort(arr: &mut [i32]) {
    if arr.len() [1] 1 {
        let pivot_index = partition(arr);
        quicksort(&mut arr[0..[2]]);
        quicksort(&mut arr[[3]..arr.len()]);
    }
}

Drag options to blanks, or click blank then click option'

A>

Bpivot_index

Cpivot_index + 1

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using < instead of > causes infinite recursion.

Swapping pivot_index and pivot_index + 1 in slices causes wrong sorting.

The base case is when length is greater than 1. The left slice ends at pivot_index, and the right slice starts at pivot_index + 1.

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