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.