Dutch National Flag Three Way Partition in DSA C

Mental Model

We rearrange an array into three parts: less than pivot, equal to pivot, and greater than pivot, all in one pass.

Analogy: Imagine sorting colored balls into three bins: red, white, and blue. You pick each ball once and put it in the correct bin without extra space.

[less] ← i -> [equal] ← j -> [unknown] ← k -> [greater]
Array: 2 0 2 1 1 0
Pointers: low, mid, high

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0], pivot = 1

Goal: Rearrange array so that all 0s come first, then all 1s, then all 2s

Step 1: Check element at mid=0 (value 2), swap with element at high=5 (value 0), decrease high

Array: [0, 0, 2, 1, 1, 2]
low=0, mid=0, high=4

Why: 2 is greater than pivot, so move it to the end

Step 2: Check element at mid=0 (value 0), swap with element at low=0 (same), increase low and mid

Array: [0, 0, 2, 1, 1, 2]
low=1, mid=1, high=4

Why: 0 is less than pivot, so move it to the front

Step 3: Check element at mid=1 (value 0), swap with element at low=1 (same), increase low and mid

Array: [0, 0, 2, 1, 1, 2]
low=2, mid=2, high=4

Why: 0 is less than pivot, so move it to the front

Step 4: Check element at mid=2 (value 2), swap with element at high=4 (value 1), decrease high

Array: [0, 0, 1, 1, 2, 2]
low=2, mid=2, high=3

Why: 2 is greater than pivot, so move it to the end

Step 5: Check element at mid=2 (value 1), equal to pivot, increase mid

Array: [0, 0, 1, 1, 2, 2]
low=2, mid=3, high=3

Why: 1 is equal to pivot, so keep it in the middle

Step 6: Check element at mid=3 (value 1), equal to pivot, increase mid

Array: [0, 0, 1, 1, 2, 2]
low=2, mid=4, high=3

Why: 1 is equal to pivot, so keep it in the middle

Result:

Array: [0, 0, 1, 1, 2, 2]

Annotated Code

DSA C

#include <stdio.h>

void dutch_national_flag_partition(int arr[], int size, int pivot) {
    int low = 0, mid = 0, high = size - 1;
    while (mid <= high) {
        if (arr[mid] < pivot) {
            int temp = arr[low];
            arr[low] = arr[mid];
            arr[mid] = temp;
            low++;
            mid++;
        } else if (arr[mid] == pivot) {
            mid++;
        } else { // arr[mid] > pivot
            int temp = arr[mid];
            arr[mid] = arr[high];
            arr[high] = temp;
            high--;
        }
    }
}

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i != size - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int size = sizeof(arr) / sizeof(arr[0]);
    int pivot = 1;
    dutch_national_flag_partition(arr, size, pivot);
    print_array(arr, size);
    return 0;
}

while (mid <= high) {

continue processing until mid passes high

if (arr[mid] < pivot) {

if current element less than pivot, swap with low and move low and mid forward

int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp; low++; mid++;

swap to move smaller element to front and advance pointers

else if (arr[mid] == pivot) { mid++; }

if equal to pivot, just move mid forward

else { int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp; high--; }

if greater than pivot, swap with high and decrease high pointer

Output

0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer moving forward

Space: O(1) because partitioning is done in place without extra storage

vs Alternative: Compared to sorting the whole array O(n log n), this is faster and uses no extra space

Edge Cases

empty array

function does nothing and array remains empty

DSA C

while (mid <= high) {

all elements equal to pivot

mid moves through entire array without swaps, array unchanged

DSA C

else if (arr[mid] == pivot) { mid++; }

array with only elements less than pivot

all elements swapped to front, effectively unchanged order

DSA C

if (arr[mid] < pivot) {

array with only elements greater than pivot

all elements swapped to end, order reversed among them

DSA C

else { int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp; high--; }

When to Use This Pattern

When you need to separate an array into three groups around a pivot in one pass, use Dutch National Flag partition to do it efficiently.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high pointer
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Using two pointers instead of three, missing the equal group
Fix: Use three pointers: low, mid, and high to separate less, equal, and greater groups

Summary

Rearranges array into three parts: less than, equal to, and greater than a pivot value.

Use when you want to partition data into three categories efficiently in one pass.

The key is to use three pointers to track boundaries and swap elements accordingly without extra space.

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