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

Dutch National Flag Three Way Partition

📖 Scenario: You are organizing colored balls in a line. The balls can be red, white, or blue. You want to arrange them so that all red balls come first, then white balls, and finally blue balls.

🎯 Goal: Build a program that rearranges an array of integers representing colors (0 for red, 1 for white, 2 for blue) so that all 0s come first, then 1s, then 2s. This is called the Dutch National Flag problem.

📋 What You'll Learn

Create an integer array called colors with the values: 2, 0, 2, 1, 1, 0

Create an integer variable pivot and set it to 1

Implement the Dutch National Flag partition algorithm using low, mid, and high pointers

Print the array after partitioning in the format: 0 0 1 1 2 2

💡 Why This Matters

🌍 Real World

Sorting colored objects or categorizing items into three groups quickly is useful in games, graphics, and inventory management.

💼 Career

Understanding partitioning algorithms like Dutch National Flag helps in coding interviews and optimizing sorting tasks in software development.

1

Create the initial array

Create an integer array called colors with these exact values: 2, 0, 2, 1, 1, 0

DSA C

# Create the array colors with values 2, 0, 2, 1, 1, 0
// 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

#include 

int main() {
    int colors[] = {2, 0, 2, 1, 1, 0};
    // Create pivot variable and set to 1
    // Your code here
    return 0;
}

Hint

Use int pivot = 1; to create the pivot variable.

3

Implement the Dutch National Flag partition

Use integer variables low, mid, and high. Initialize low and mid to 0, and high to 5. Use a while loop with condition mid <= high. Inside the loop, if colors[mid] is less than pivot, swap colors[low] and colors[mid], then increment low and mid. If colors[mid] equals pivot, increment mid. Otherwise, swap colors[mid] and colors[high], then decrement high.

DSA C

#include 

int main() {
    int colors[] = {2, 0, 2, 1, 1, 0};
    int pivot = 1;
    // Implement Dutch National Flag partition
    // Your code here
    return 0;
}

Hint

Use three pointers low, mid, high and swap elements based on comparison with pivot.

4

Print the partitioned array

Use a for loop with variable i from 0 to 5 to print each element of colors separated by spaces on one line.

DSA C

#include 

int main() {
    int colors[] = {2, 0, 2, 1, 1, 0};
    int pivot = 1;
    int low = 0, mid = 0, high = 5;
    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--;
        }
    }
    // Print the colors array
    // Your code here
    return 0;
}

Hint

Use a for loop to print each element separated by spaces.

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 using quicksort

B. To rearrange an array into three parts: less than, equal to, and greater than a pivot

C. To find the maximum element in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the partitioning goal

   The algorithm divides the array into three parts based on a pivot value: elements less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Compare with other options

   Options A, C, and D describe different operations: sorting, finding max, and reversing, which are not the main goal here.

3. Final Answer:

   To rearrange an array into three parts: less than, equal to, and greater than a pivot -> Option B

4. Quick Check:

   Partitioning = three parts [OK]

Hint: Remember: three parts based on pivot value [OK]

Common Mistakes:

• Confusing with full sorting algorithms
• Thinking it only separates two parts
• Assuming it finds max or min values

2. Which of the following is the correct way to declare the pointers used in the Dutch National Flag algorithm in C?

easy

A. int low = 0, mid = 0, high = n - 1;

B. int low, mid, high = 0;

C. int low = n, mid = 0, high = n - 1;

D. int low = 0, mid = n - 1, high = 0;

Solution

1. Step 1: Understand pointer initialization

   In the algorithm, low and mid start at 0, and high starts at n-1 (last index).

2. Step 2: Check each option

   int low = 0, mid = 0, high = n - 1; correctly initializes low and mid to 0, high to n-1. Others have incorrect initial values.

3. Final Answer:

   int low = 0, mid = 0, high = n - 1; -> Option A

4. Quick Check:

   Pointers start: low=0, mid=0, high=n-1 [OK]

Hint: Initialize low and mid at 0, high at last index [OK]

Common Mistakes:

• Setting low or mid to n or n-1 incorrectly
• Not initializing all pointers
• Confusing variable assignments

3. What will be the output array after applying the Dutch National Flag algorithm on arr = {2, 0, 2, 1, 1, 0} with pivot = 1?

medium

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

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

C. [1, 1, 0, 0, 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

   So the array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Group less, equal, greater around pivot [OK]

Common Mistakes:

• Mixing order of groups
• Not grouping equal elements correctly
• Assuming full sorting instead of partitioning

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

void dnfPartition(int arr[], int n, int pivot) {
  int low = 0, mid = 0, high = n - 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. Pivot comparison should use > instead of <

B. The loop condition should be mid < high

C. Pointers low and mid should start at n-1

D. swap function is not defined for array elements

Solution

1. Step 1: Check swap usage

   The code uses swap(arr[low], arr[mid]) but swap is not a built-in function in C for array elements.

2. Step 2: Verify other parts

   Loop condition and pointer initialization are correct. Pivot comparisons are correct as per algorithm.

3. Final Answer:

   swap function is not defined for array elements -> Option D

4. Quick Check:

   Missing swap definition = error [OK]

Hint: Remember to define or implement swap for array elements [OK]

Common Mistakes:

• Assuming swap is built-in for arrays in C
• Changing loop condition incorrectly
• Wrong pointer initialization

5. Given an array arr = {3, 5, 2, 3, 8, 3, 1, 3} and pivot = 3, how many swaps will the Dutch National Flag algorithm perform to partition the array?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Trace swaps during partition

   Initial pointers: low=0, mid=0, high=7. - mid=0 (3 == pivot): mid++ (0 swaps) - mid=1 (5 > pivot): swap arr[mid] and arr[high] -> swap(5,3), high=6 (1 swap) - mid=1 (now 3 == pivot): mid++ (1 swap) - mid=2 (2 < pivot): swap arr[low] and arr[mid] -> swap(3,2), low=1, mid=3 (2 swaps) - mid=3 (3 == pivot): mid++ (2 swaps) - mid=4 (8 > pivot): swap arr[mid] and arr[high] -> swap(8,1), high=5 (3 swaps) - mid=4 (now 1 < pivot): swap arr[low] and arr[mid] -> swap(3,1), low=2, mid=5 (4 swaps) - mid=5 (3 == pivot): mid++ (4 swaps) Loop ends as mid=6 > high=5.

2. Step 2: Count total swaps

   Total swaps performed = 4

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count swaps carefully = 4 [OK]

Hint: Count swaps during each pointer move carefully [OK]

Common Mistakes:

• Counting swaps only when mid moves
• Ignoring swaps after swapping with high
• Miscounting swaps when elements equal pivot