Quick Sort Algorithm in DSA Rust - Execution Trace

Concept Flow - Quick Sort Algorithm

Choose pivot element

↓

Partition array around pivot

↓

Elements < pivot to left

↓

Elements > pivot to right

↓

Recursively quick sort left part

→Recursively quick sort right part

↓

Combine results

Quick Sort picks a pivot, partitions the array around it, then sorts left and right parts recursively.

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 partitioning around a pivot and recursively sorting subarrays.

Execution Table

Step	Operation	Pivot	Array State	Partition Result	Notes
1	Start quick_sort	-	[8, 3, 7, 6, 2]	-	Initial array
2	Choose pivot	2	[8, 3, 7, 6, 2]	-	Pivot chosen as last element
3	Partitioning	2	[8, 3, 7, 6, 2]	[2, 3, 7, 6, 8]	Elements rearranged around pivot
4	Pivot placed at index 0	2	[2, 3, 7, 6, 8]	Pivot index = 0	Pivot in correct position
5	Recurse left part	-	[]	-	Left subarray empty, base case hit
6	Recurse right part	-	[3, 7, 6, 8]	-	Sort right subarray
7	Choose pivot	8	[3, 7, 6, 8]	-	Pivot chosen as last element
8	Partitioning	8	[3, 7, 6, 8]	[3, 7, 6, 8]	All elements less than pivot
9	Pivot placed at index 3	8	[3, 7, 6, 8]	Pivot index = 3	Pivot in correct position
10	Recurse left part	-	[3, 7, 6]	-	Sort left subarray
11	Recurse right part	-	[]	-	Right subarray empty, base case hit
12	Choose pivot	6	[3, 7, 6]	-	Pivot chosen as last element
13	Partitioning	6	[3, 7, 6]	[3, 6, 7]	Elements rearranged around pivot
14	Pivot placed at index 1	6	[3, 6, 7]	Pivot index = 1	Pivot in correct position
15	Recurse left part	-	[3]	-	Single element, base case hit
16	Recurse right part	-	[7]	-	Single element, base case hit
17	All recursive calls done	-	[2, 3, 6, 7, 8]	-	Array fully sorted

💡 Recursion ends when subarrays have 0 or 1 element (base case).

Variable Tracker

Variable	Start	After Step 3	After Step 9	After Step 14	Final
arr	[8, 3, 7, 6, 2]	[2, 3, 7, 6, 8]	[2, 3, 7, 6, 8]	[2, 3, 6, 7, 8]	[2, 3, 6, 7, 8]
pivot	-	2	8	6	-
pivot_index	-	0	3	1	-

Key Moments - 3 Insights

Why does the pivot end up in its correct sorted position after partitioning?

Because partitioning moves all smaller elements to the left and larger to the right, placing the pivot between them (see Step 4, 9, 14 in execution_table).

What happens when the subarray has zero or one element?

The recursion stops immediately as these are base cases (see Steps 5, 11, 15, 16). No further sorting needed.

Why do we sort the parts left and right of the pivot separately?

Because the pivot is already in correct place, sorting left and right parts recursively sorts the whole array (see Steps 6, 10, 12).

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the array state after partitioning around pivot 2?

A [2, 3, 7, 6, 8]

B [8, 3, 7, 6, 2]

C [3, 7, 6, 8, 2]

D [2, 8, 3, 7, 6]

💡 Hint

Check the 'Array State' column at Step 3 in execution_table.

At which step does the pivot 6 get placed in its correct position?

A Step 4

B Step 9

C Step 14

D Step 3

💡 Hint

Look for 'Pivot placed at index' with pivot 6 in execution_table.

If the initial array was already sorted, how would the partitioning steps change?

A Pivot would be smallest element, causing many swaps.

B Pivot would always be the largest element, partitioning would not swap elements.

C Partitioning would fail and cause infinite recursion.

D Pivot would be in the middle, splitting array evenly.

💡 Hint

Consider how partitioning behaves when all elements are less than or equal to pivot.

Concept Snapshot

Quick Sort Algorithm:
- Pick a pivot (often last element).
- Partition array: smaller left, larger right.
- Recursively sort left and right parts.
- Base case: subarray size ≤ 1.
- Efficient average O(n log n) sorting.

Full Transcript

Quick Sort works by choosing a pivot element and rearranging the array so that elements smaller than the pivot come before it and larger elements come after. This is called partitioning. After partitioning, the pivot is in its correct sorted position. Then, Quick Sort recursively sorts the left and right subarrays around the pivot. The recursion stops when subarrays have zero or one element, which are already sorted. This process efficiently sorts the entire array. The execution table shows each step of choosing pivots, partitioning, and recursive calls, with the array state changing until fully sorted.

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