Quick Sort as Divide and Conquer in DSA Rust - Execution Trace

Concept Flow - Quick Sort as Divide and Conquer

Choose pivot element

↓

Partition array into < pivot | pivot | > pivot

↓

Recursively quick sort left part

↓

Recursively quick sort right part

↓

Combine sorted parts

↓

Sorted array ready

Quick Sort picks a pivot, splits the array into smaller and bigger parts, sorts those parts separately, then joins them back.

Execution Sample

DSA Rust

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 { return; }
    let pivot_index = partition(arr);
    quick_sort(&mut arr[..pivot_index]);
    quick_sort(&mut arr[pivot_index + 1..]);
}

This code sorts an array by picking a pivot, partitioning, then sorting left and right parts recursively.

Execution Table

Step	Operation	Array State	Pivot Chosen	Partition Result	Visual State
1	Start quick_sort on [3, 7, 6, 2, 8]	[3, 7, 6, 2, 8]	8 (last element)	Partition around 8	[3, 7, 6, 2, 8]
2	Partitioning: compare 3,7,6,2 with 8	[3, 7, 6, 2, 8]	8	All < 8, pivot placed at index 4	[3, 7, 6, 2, 8]
3	Recurse left part [3, 7, 6, 2]	[3, 7, 6, 2]	2 (last element)	Partition around 2	[3, 7, 6, 2]
4	Partitioning: compare 3,7,6 with 2	[3, 7, 6, 2]	2	No elements < 2, pivot at index 0	[2, 7, 6, 3]
5	Recurse left part [] (empty)	[]	-	-	[]
6	Recurse right part [7, 6, 3]	[7, 6, 3]	3 (last element)	Partition around 3	[7, 6, 3]
7	Partitioning: compare 7,6 with 3	[7, 6, 3]	3	No elements < 3, pivot at index 0	[3, 6, 7]
8	Recurse left part [] (empty)	[]	-	-	[]
9	Recurse right part [6,7]	[6,7]	7 (last element)	Partition around 7	[6,7]
10	Partitioning: compare 6 with 7	[6,7]	7	6 < 7, pivot at index 1	[6,7]
11	Recurse left part [6]	[6]	-	-	[6]
12	Recurse right part [] (empty)	[]	-	-	[]
13	Combine all parts	[2, 3, 6, 7, 8]	-	-	[2, 3, 6, 7, 8]

💡 Recursion ends when sub-array length is 0 or 1, meaning it's sorted.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 10	Final
arr	[3, 7, 6, 2, 8]	[3, 7, 6, 2, 8]	[2, 7, 6, 3]	[3, 6, 7]	[6, 7]	[2, 3, 6, 7, 8]
pivot_index	N/A	4	0	0	1	N/A
sub-array left	N/A	[3, 7, 6, 2]	[]	[]	[6]	N/A
sub-array right	N/A	[]	[7, 6, 3]	[6, 7]	[]	N/A

Key Moments - 3 Insights

Why does the pivot sometimes end up at the start of the sub-array?

Because during partition, if no elements are smaller than pivot, it stays at the start. See steps 4 and 7 in execution_table where pivot_index is 0.

Why do we stop recursion when sub-array length is 0 or 1?

Because arrays with 0 or 1 element are already sorted. This is shown in steps 5, 8, 11, and 12 where recursion ends.

How does partition rearrange elements around the pivot?

Partition moves all smaller elements before pivot and larger after. For example, step 2 shows elements less than 8 moved left, pivot placed at index 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the pivot_index after partition?

A 4

B 2

C 0

D 3

💡 Hint

Check the 'Pivot Chosen' and 'Partition Result' columns at step 4.

At which step does the array become fully sorted?

A Step 13

B Step 11

C Step 10

D Step 7

💡 Hint

Look at the 'Visual State' column for the final sorted array.

If the pivot was chosen as the first element instead of last, how would step 2 change?

A Pivot would be 8, partitioning same as now

B Pivot would be 3, partitioning changes

C Pivot would be 2, partitioning changes completely

D Pivot would be 8, but partitioning order changes

💡 Hint

Pivot choice affects partitioning; step 2 shows pivot as last element.

Concept Snapshot

Quick Sort divides array by pivot
Partition moves smaller left, bigger right
Recursively sort left and right parts
Stop when sub-array size ≤ 1
Combine parts for sorted array

Full Transcript

Quick Sort works by picking a pivot element, usually the last element in the current array. It then rearranges the array so that all elements smaller than the pivot come before it, and all larger come after. This is called partitioning. After partitioning, the pivot is in its correct sorted position. The algorithm then repeats this process recursively on the left and right sub-arrays around the pivot. Recursion stops when the sub-array has zero or one element, which is already sorted. Finally, all parts combine to form the fully sorted array. This divide and conquer approach efficiently sorts the array step-by-step.

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