Quick Sort as Divide and Conquer in DSA Rust

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, then combines them to get a sorted list.

Analogy: Imagine sorting a deck of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side separately.

Array: [7, 2, 5, 3, 9]
Pivot chosen -> 5
Split into:
Left: [2, 3]
Pivot: [5]
Right: [7, 9]

Dry Run Walkthrough

Input: list: [7, 2, 5, 3, 9]

Goal: Sort the list in ascending order using Quick Sort

Step 1: Choose pivot 9 (last element), partition array

[7, 2, 5, 3, 9]
Pivot=9
Partitioned into left ≤9 and right >9
All elements ≤9, so no change

Why: Pivot divides array into smaller and bigger parts

Step 2: Recursively quicksort left part [7, 2, 5, 3]

[7, 2, 5, 3]
Pivot=3
Partition into ≤3 and >3
Left: [2, 3]
Right: [7, 5]

Why: Sort smaller parts separately

Step 3: Recursively quicksort left part [2, 3]

[2, 3]
Pivot=3
Partition: left ≤3 is [2], right >3 is []

Why: Base case reached for small parts

Step 4: Recursively quicksort right part [7, 5]

[7, 5]
Pivot=5
Partition: left ≤5 is [5], right >5 is [7]

Why: Sort right part around pivot

Step 5: Combine sorted parts: [2, 3] + [5] + [7] + [9]

[2, 3, 5, 7, 9]

Why: Merging sorted parts gives fully sorted array

Result:

[2, 3, 5, 7, 9]

Annotated Code

DSA Rust

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return; // base case: array is sorted
    }
    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(left);
    quick_sort(&mut right[1..]);
}

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); // swap smaller element to front
            i += 1; // move boundary of smaller elements
        }
    }
    arr.swap(i, arr.len() - 1); // place pivot in correct position
    i // return pivot index
}

fn main() {
    let mut data = [7, 2, 5, 3, 9];
    quick_sort(&mut data);
    for val in data.iter() {
        print!("{} ", val);
    }
    println!();
}

if arr.len() <= 1 { return; }

stop recursion when array is size 1 or empty

let pivot_index = partition(arr);

partition array around pivot and get pivot position

let (left, right) = arr.split_at_mut(pivot_index);

split array into left and right parts at pivot

quick_sort(left);

recursively sort left part

quick_sort(&mut right[1..]);

recursively sort right part excluding pivot

for j in 0..arr.len() - 1 { if arr[j] <= pivot { arr.swap(i, j); i += 1; } }

move elements smaller or equal to pivot to front

arr.swap(i, arr.len() - 1);

place pivot in its correct sorted position

Output

2 3 5 7 9 

Complexity Analysis

Time: O(n log n) average case because each partition splits array roughly in half and sorting happens recursively

Space: O(log n) due to recursion stack depth in average case

vs Alternative: Better than simple sorting like bubble sort O(n²) because it divides problem and conquers smaller parts efficiently

Edge Cases

empty array

function returns immediately without changes

DSA Rust

if arr.len() <= 1 { return; }

array with one element

function returns immediately as array is already sorted

DSA Rust

if arr.len() <= 1 { return; }

array with all equal elements

partition keeps elements in place, recursion ends quickly

DSA Rust

if arr.len() <= 1 { return; }

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently by splitting into smaller parts, reach for Quick Sort because it uses divide and conquer to sort fast.

Common Mistakes

Mistake: Not excluding the pivot element from the right recursive call causing infinite recursion
Fix: Call quick_sort on right[1..] to skip the pivot element

Mistake: Choosing pivot but not placing it in correct position after partition
Fix: Swap pivot with element at partition index to place it correctly

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you want an efficient, average O(n log n) sorting algorithm.

The key insight is dividing the problem into smaller parts around a pivot and conquering each part separately.

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