Quick Sort Algorithm in DSA Rust

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of books by picking one book as a reference, then putting all smaller books to the left and bigger books to the right, then repeating this for each side until all books are in order.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 3
Partitioned: [2, 3, 9, 4, 7]
Left side: [2]
Right side: [9, 4, 7]

Dry Run Walkthrough

Input: array: [7, 2, 9, 4, 3]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 3, partition array around pivot

[7, 2, 9, 4, 3]
Pivot=3
Partitioning...

Why: Pivot divides array into smaller and bigger parts

Step 2: Swap elements to place smaller than pivot left, bigger right

[2, 3, 9, 4, 7]
Pivot=3 placed at index 1

Why: Ensures pivot is in correct sorted position

Step 3: Recursively quick sort left subarray [2]

[2]
Single element, already sorted

Why: Base case reached, no further sorting needed

Step 4: Recursively quick sort right subarray [9, 4, 7]

[9, 4, 7]
Choose pivot=7

Why: Sort right side similarly

Step 5: Partition right subarray around pivot 7

[4, 7, 9]
Pivot=7 placed at index 1

Why: Pivot placed correctly in right subarray

Step 6: Recursively quick sort left subarray [4]

[4]
Single element, sorted

Why: Base case reached

Step 7: Recursively quick sort right subarray [9]

[9]
Single element, sorted

Why: Base case reached

Result:

Final sorted array: [2, 3, 4, 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);
    quick_sort(&mut arr[..pivot_index]); // sort left side
    quick_sort(&mut arr[pivot_index + 1..]); // sort right side
}

fn partition(arr: &mut [i32]) -> usize {
    let pivot = arr[arr.len() - 1]; // choose last element as pivot
    let mut i = 0; // place for swapping smaller elements
    for j in 0..arr.len() - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j); // swap smaller or equal element to front
            i += 1; // move swap position forward
        }
    }
    arr.swap(i, arr.len() - 1); // place pivot in correct position
    i // return pivot index
}

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

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

stop recursion when array has 0 or 1 element

let pivot_index = partition(arr);

divide array around pivot and get pivot position

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

recursively sort left subarray

quick_sort(&mut arr[pivot_index + 1..]);

recursively sort right subarray

let pivot = arr[arr.len() - 1];

choose last element as pivot

if arr[j] <= pivot { arr.swap(i, j); i += 1; }

move smaller or equal elements to front

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

place pivot in correct sorted position

Output

2 3 4 7 9 

Complexity Analysis

Time: O(n log n) average case because the array is split into halves recursively and each element is compared once per level

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

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides and conquers instead of comparing all pairs

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 places pivot but no swaps needed, recursion ends quickly

DSA Rust

if arr[j] <= pivot { arr.swap(i, j); i += 1; }

When to Use This Pattern

When you see a problem asking to sort efficiently with divide and conquer, reach for Quick Sort because it splits the problem around a pivot and sorts parts recursively.

Common Mistakes

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

Mistake: Not handling base case of array length 0 or 1, causing infinite recursion
Fix: Add condition to return immediately if array length is 0 or 1

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-case sorting algorithm with good performance on large arrays.

The key insight is placing the pivot in its correct position so smaller elements go left and bigger go right, then sorting those parts separately.

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