Why Dutch National Flag Three Way Partition in DSA Rust?

The Big Idea

What if you could sort three groups in one quick sweep without confusion or extra space?

The Scenario

Imagine you have a box of colored balls mixed together: red, white, and blue. You want to sort them so all reds come first, then whites, then blues. Doing this by picking one ball at a time and placing it in the right spot by hand is tiring and slow.

The Problem

Manually sorting each ball means checking every ball multiple times, moving them around again and again. This wastes time and can cause mistakes, like mixing colors or missing some balls. It's hard to keep track when the box is big.

The Solution

The Dutch National Flag algorithm sorts the balls in just one pass. It smartly swaps balls to their correct places without extra space or repeated checks. This makes sorting fast, simple, and error-free.

Before vs After

✗ Before

let mut balls = vec![0u8, 2u8, 1u8, 0u8];
balls.sort();

✓ After

fn dutch_national_flag_partition(balls: &mut [u8]) {
    let mut low = 0;
    let mut mid = 0;
    let mut high = balls.len().saturating_sub(1);
    while mid <= high {
        match balls[mid] {
            0 => { balls.swap(low, mid); low += 1; mid += 1; },
            1 => mid += 1,
            2 => { balls.swap(mid, high); if high == 0 { break; } high -= 1; },
            _ => { mid += 1; }
        }
    }
}

What It Enables

This method lets you quickly and cleanly separate three groups in a list with just one pass, saving time and effort.

Real Life Example

Sorting socks by color in a drawer: whites, blacks, and colored socks. Using this method, you can organize them fast without mixing colors.

Key Takeaways

Manual sorting is slow and error-prone for three groups.

Dutch National Flag algorithm sorts in one pass with swaps.

It saves time and avoids mistakes in grouping items.

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To sort an array in ascending order

B. To reverse the elements of an array

C. To find the maximum element in an array

D. To rearrange an array into three parts based on a pivot value

Solution

1. Step 1: Understand the problem goal

   The algorithm divides the array into three parts: less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Compare with other options

   Sorting or finding max are different tasks; reversing is unrelated.

3. Final Answer:

   To rearrange an array into three parts based on a pivot value -> Option D

4. Quick Check:

   Partitioning by pivot = rearrange into three parts [OK]

Hint: Remember: Dutch Flag splits array into three color groups [OK]

Common Mistakes:

• Confusing partition with full sorting
• Thinking it finds max or min values
• Assuming it reverses the array

2. Which of the following Rust code snippets correctly declares mutable indices for the Dutch National Flag algorithm?

easy

A. let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1;

B. let low = 0; let mid = 0; let high = arr.len() - 1;

C. let mut low = 0; let mid = 0; let mut high = arr.len() - 1;

D. let low = 0; let mut mid = 0; let high = arr.len() - 1;

Solution

1. Step 1: Identify mutability requirement

   Indices must be mutable to update during partitioning.

2. Step 2: Check each declaration

   Only let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1; declares all three indices as mutable.

3. Final Answer:

   let mut low = 0; let mut mid = 0; let mut high = arr.len() - 1; -> Option A

4. Quick Check:

   All indices mutable = correct declaration [OK]

Hint: Indices change, so declare all as mutable with 'mut' [OK]

Common Mistakes:

• Forgetting 'mut' keyword for variables that change
• Mixing mutable and immutable declarations incorrectly
• Using immutable variables causing compile errors

3. What will be the output of the following Rust code after applying the Dutch National Flag partition with pivot = 1?

let mut arr = vec![2, 0, 2, 1, 1, 0];
let pivot = 1;
// After partitioning
// arr = ?

medium

A. [1, 1, 0, 0, 2, 2]

B. [0, 0, 1, 1, 2, 2]

C. [2, 2, 1, 1, 0, 0]

D. [0, 1, 0, 1, 2, 2]

Solution

1. Step 1: Understand partitioning by pivot 1

   Elements less than 1 go first (0s), then equal to 1, then greater than 1 (2s).

2. Step 2: Rearrange array accordingly

   Original: [2, 0, 2, 1, 1, 0] After partition: [0, 0, 1, 1, 2, 2]

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option B

4. Quick Check:

   Partitioned array = [0, 0, 1, 1, 2, 2] [OK]

Hint: Group elements less, equal, then greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of less and greater groups
• Assuming full sorting instead of partitioning

4. Identify the bug in this Rust code snippet implementing Dutch National Flag partition:

let mut low = 0;
let mut mid = 0;
let mut high = arr.len() - 1;
while mid <= high {
    if arr[mid] < pivot {
        arr.swap(low, mid);
        low += 1;
        mid += 1;
    } else if arr[mid] == pivot {
        mid += 1;
    } else {
        arr.swap(mid, high);
        high -= 1;
    }
}

medium

A. mid should be decremented in else block

B. Incorrect comparison operators for pivot

C. Missing increment of mid after swapping with low

D. high should be incremented instead of decremented

Solution

1. Step 1: Analyze pointer updates after swaps

   When swapping arr[low] and arr[mid], mid must also move forward to avoid infinite loop.

2. Step 2: Identify missing mid increment

   Code increments mid only when arr[mid] == pivot, but not after swapping with low.

3. Final Answer:

   Missing increment of mid after swapping with low -> Option C

4. Quick Check:

   mid must increment after swap with low to progress [OK]

Hint: Increment mid after swapping with low to avoid infinite loop [OK]

Common Mistakes:

• Forgetting to increment mid after swap with low
• Changing mid incorrectly in else block
• Misunderstanding pointer movements

5. Given an array with elements 0, 1, and 2 representing colors red, white, and blue respectively, how would you modify the Dutch National Flag algorithm to sort the array so that all reds come first, whites second, and blues last? Choose the correct approach.

hard

A. Use three pointers low, mid, high; move mid forward, swap with low if 0, swap with high if 2.

B. Sort the array using Rust's built-in sort() method.

C. Use two pointers only, swapping elements when needed.

D. Count the number of 0s, 1s, and 2s, then overwrite the array accordingly.

Solution

1. Step 1: Understand the Dutch National Flag approach

   It uses three pointers to partition the array into three parts efficiently in one pass.

2. Step 2: Compare with other methods

   Built-in sort or counting are valid but not the Dutch National Flag algorithm; two pointers are insufficient for three groups.

3. Final Answer:

   Use three pointers low, mid, high; move mid forward, swap with low if 0, swap with high if 2. -> Option A

4. Quick Check:

   Three pointers and swaps = Dutch National Flag method [OK]

Hint: Three pointers: low, mid, high handle 0,1,2 in one pass [OK]

Common Mistakes:

• Using sorting instead of partitioning
• Trying two pointers for three groups
• Ignoring efficient one-pass solution