Quick Sort as Divide and Conquer in DSA Rust - Build from Scratch

Quick Sort as Divide and Conquer

📖 Scenario: You have a list of numbers that you want to sort from smallest to largest. Sorting helps you find things faster, like organizing books by their height on a shelf.

🎯 Goal: You will build a simple program in Rust that uses the Quick Sort method to sort a list of numbers. Quick Sort works by picking a number, then putting smaller numbers on one side and bigger numbers on the other, and repeating this until everything is sorted.

📋 What You'll Learn

Create a vector called numbers with these exact values: 29, 10, 14, 37, 13

Create a function called quick_sort that takes a mutable slice of i32 numbers

Inside quick_sort, implement the divide and conquer logic using recursion and partitioning

Call quick_sort on the entire numbers vector

Print the sorted numbers vector

💡 Why This Matters

🌍 Real World

Sorting is used everywhere, like organizing files, searching data quickly, or arranging products by price in online stores.

💼 Career

Understanding Quick Sort helps in software development roles where efficient data handling and algorithm knowledge are important.

1

Create the initial list of numbers

Create a vector called numbers with these exact values: 29, 10, 14, 37, 13

DSA Rust

# Create a vector called numbers with the values 29, 10, 14, 37, 13
# Your code here

Hint

Use let mut numbers = vec![29, 10, 14, 37, 13]; to create the vector.

2

Add the quick_sort function signature

Add a function called quick_sort that takes a mutable slice of i32 numbers as arr: &mut [i32]

DSA Rust

fn main() {
    let mut numbers = vec![29, 10, 14, 37, 13];
}

// Add the quick_sort function signature below
// Your code here

Hint

Define the function with fn quick_sort(arr: &mut [i32]) {}.

3

Implement the quick_sort logic with partitioning and recursion

Inside the quick_sort function, implement the divide and conquer logic: if the slice length is less than 2, return; otherwise, partition the slice around a pivot and recursively call quick_sort on the left and right parts

DSA Rust

fn main() {
    let mut numbers = vec![29, 10, 14, 37, 13];
}

fn quick_sort(arr: &mut [i32]) {
    // Implement quick sort logic here
    // Your code here
}

Hint

Use a helper function partition to reorder elements and return the pivot index. Then recursively sort left and right parts.

4

Call quick_sort and print the sorted vector

Call quick_sort on the entire numbers vector and then print numbers using println!("{:?}", numbers);

DSA Rust

fn main() {
    let mut numbers = vec![29, 10, 14, 37, 13];
    // Call quick_sort on numbers
    // Print numbers
    // Your code here
}

fn quick_sort(arr: &mut [i32]) {
    if arr.len()  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
}

Hint

Call quick_sort(&mut numbers); and then print with println!("{:?}", numbers);.

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