Dutch National Flag Three Way Partition in DSA C# - Build from Scratch

Dutch National Flag Three Way Partition

📖 Scenario: Imagine you have a row of colored balls represented by numbers: 0 for red, 1 for white, and 2 for blue. You want to sort them so that all reds come first, then whites, and then blues, just like the Dutch flag.

🎯 Goal: You will write a program that rearranges an array of numbers containing only 0s, 1s, and 2s so that all 0s come first, then all 1s, and then all 2s.

📋 What You'll Learn

Create an integer array called colors with the exact values {2, 0, 2, 1, 1, 0}.

Create an integer variable called pivot and set it to 1.

Implement the Dutch National Flag partition algorithm using low, mid, and high pointers to reorder colors around pivot.

Print the colors array after partitioning in the format: 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null.

💡 Why This Matters

🌍 Real World

Sorting items into categories quickly is useful in many real-world tasks like organizing products by type or sorting colors in graphics.

💼 Career

Understanding partitioning algorithms like Dutch National Flag is important for software engineers working on sorting, searching, and optimization problems.

1

Create the initial array

Create an integer array called colors with the exact values {2, 0, 2, 1, 1, 0}.

DSA C#

# Your code here

Hint

Use int[] colors = {2, 0, 2, 1, 1, 0}; to create the array.

2

Set the pivot value

Create an integer variable called pivot and set it to 1.

DSA C#

int[] colors = {2, 0, 2, 1, 1, 0};
# Your code here

Hint

Use int pivot = 1; to set the pivot.

3

Implement the Dutch National Flag partition

Use integer variables low, mid, and high to reorder the colors array around the pivot using a while loop. Swap elements to ensure all values less than pivot come first, then equal to pivot, then greater than pivot.

DSA C#

int[] colors = {2, 0, 2, 1, 1, 0};
int pivot = 1;
# Your code here

Hint

Use three pointers and swap elements to reorder the array in one pass.

4

Print the partitioned array

Print the colors array after partitioning in the format: 0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null.

DSA C#

int[] colors = {2, 0, 2, 1, 1, 0};
int pivot = 1;

int low = 0;
int mid = 0;
int high = colors.Length - 1;

while (mid <= high)
{
    if (colors[mid] < pivot)
    {
        int temp = colors[low];
        colors[low] = colors[mid];
        colors[mid] = temp;
        low++;
        mid++;
    }
    else if (colors[mid] == pivot)
    {
        mid++;
    }
    else
    {
        int temp = colors[mid];
        colors[mid] = colors[high];
        colors[high] = temp;
        high--;
    }
}

# Your code here

Hint

Use a for loop to print each element followed by " -> ", then print "null" at the end.

Practice

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

easy

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

B. To sort an array in ascending order

C. To find the maximum element in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the algorithm's purpose

   The Dutch National Flag algorithm partitions an array into three parts: less than, equal to, and greater than a 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 A

4. Quick Check:

   Partitioning = Rearranging into three parts [OK]

Hint: Remember: It splits array into three groups around a pivot [OK]

Common Mistakes:

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

2. Which of the following is the correct C# syntax to swap two elements arr[i] and arr[j] in an array?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr.Swap(i, j);

Solution

1. Step 1: Understand swapping in C# arrays

   Swapping requires a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly; B overwrites values; C and D are invalid syntax in C#.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Swap needs temp variable [OK]

Hint: Use a temp variable to swap two array elements [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using non-existent swap functions
• Confusing syntax from other languages

3. What will be the output array after applying the Dutch National Flag partition on arr = [2, 0, 2, 1, 1, 0] with pivot = 1?

medium

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

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

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

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

Solution

1. Step 1: Partition array around pivot 1

   Elements less than 1: 0,0; equal to 1: 1,1; greater than 1: 2,2.

2. Step 2: Arrange in order less, equal, greater

   Resulting array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

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 groups
• Ignoring pivot value placement

4. Identify the error in this C# code snippet for Dutch National Flag partition:

int low = 0, mid = 0, high = arr.Length - 1;
while (mid <= high) {
  if (arr[mid] < pivot) {
    Swap(arr[low], arr[mid]);
    low++;
    mid++;
  } else if (arr[mid] == pivot) {
    mid++;
  } else {
    Swap(arr[mid], arr[high]);
    high--;
  }
}

medium

A. Variables low, mid, high are not declared

B. Loop condition should be mid < high, not mid <= high

C. Pivot value is not initialized

D. Swap method is called incorrectly; should swap array elements by index

Solution

1. Step 1: Check Swap usage

   Swap(arr[low], arr[mid]) passes values, not indices; swapping values won't affect array elements.

2. Step 2: Correct swap call

   Swap should be a method swapping elements by indices or use a temp variable to swap arr[low] and arr[mid].

3. Final Answer:

   Swap method is called incorrectly; should swap array elements by index -> Option D

4. Quick Check:

   Swap must affect array elements, not just values [OK]

Hint: Swap array elements by index, not by passing values [OK]

Common Mistakes:

• Passing values instead of indices to swap
• Incorrect loop boundary conditions
• Forgetting to initialize pivot

5. Given an array arr = [3, 5, 2, 3, 8, 3, 1] and pivot = 3, how would you modify the Dutch National Flag algorithm to partition the array so that all elements less than 3 come first, then all elements equal to 3, and finally all elements greater than 3? What is the final array?

hard

A. [2, 1, 3, 3, 3, 5, 8]

B. [1, 2, 3, 3, 3, 8, 5]

C. [3, 3, 3, 2, 1, 5, 8]

D. [5, 8, 3, 3, 3, 2, 1]

Solution

1. Step 1: Apply Dutch National Flag partition with pivot 3

   Group elements less than 3: 1,2; equal to 3: 3,3,3; greater than 3: 5,8.

2. Step 2: Arrange groups in order less, equal, greater

   Final array is [2, 1, 3, 3, 3, 5, 8].

3. Final Answer:

   [2, 1, 3, 3, 3, 5, 8] -> Option A

4. Quick Check:

   Partitioned array = [2,1,3,3,3,5,8] [OK]

Hint: Place less, equal, then greater elements around pivot [OK]

Common Mistakes:

• Mixing order of groups
• Not grouping all equal elements together
• Ignoring elements equal to pivot