Dutch National Flag
In this page:
Three-way Partition Idea
The Dutch National Flag algorithm rearranges an array containing only three distinct values (commonly 0, 1, 2) into three grouped sections in a single pass, named after the three horizontal color bands of the Dutch flag.
Example: Three-way Partition Idea
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 0, 1, 2, 1, 0};
int n = 6, low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
else if (arr[mid] == 1) mid++;
else swap(arr[mid], arr[high--]);
}
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 0, 1, 2, 1, 0};
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) { int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t; low++; mid++; }
else if (arr[mid] == 1) mid++;
else { int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t; high--; }
}
for (int x : arr) System.out.print(x + " ");
}
}arr = [2, 0, 1, 2, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low += 1; mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
print(arr)#include <stdio.h>
int main() {
int arr[] = {2, 0, 1, 2, 1, 0};
int n = 6, low = 0, mid = 0, high = n - 1, t;
while (mid <= high) {
if (arr[mid] == 0) { t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
else if (arr[mid] == 1) mid++;
else { t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
}
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
Low, Mid, and High
Three pointers do the work: low marks the boundary up to which all 0s have been placed, high marks the boundary from which all 2s have been placed, and mid scans through the unprocessed middle section between them.
Example: Low, Mid, and High
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 0, 2, 1, 0};
int n = 5, low = 0, mid = 0, high = n - 1;
cout << "low=" << low << " (boundary for 0s), mid=" << mid << " (scanner), high=" << high << " (boundary for 2s)" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 0, 2, 1, 0};
int low = 0, mid = 0, high = arr.length - 1;
System.out.println("low=" + low + " (boundary for 0s), mid=" + mid + " (scanner), high=" + high + " (boundary for 2s)");
}
}arr = [1, 0, 2, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
print(f"low={low} (boundary for 0s), mid={mid} (scanner), high={high} (boundary for 2s)")#include <stdio.h>
int main() {
int arr[] = {1, 0, 2, 1, 0};
int n = 5, low = 0, mid = 0, high = n - 1;
printf("low=%d (boundary for 0s), mid=%d (scanner), high=%d (boundary for 2s)\n", low, mid, high);
return 0;
}Login to try C/C++/Java code in the editor
Handling Zero
When mid points to a 0, it's swapped with the element at low, and both low and mid advance, since the swapped-in value at mid is now guaranteed to be a 1 (already processed) or safe to check next.
Example: Handling Zero
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 0, 2};
int low = 0, mid = 1;
cout << "Before: arr[mid]=" << arr[mid] << endl;
swap(arr[low], arr[mid]);
low++; mid++;
cout << "After swap with low: arr[0]=" << arr[0] << ", low=" << low << ", mid=" << mid << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 0, 2};
int low = 0, mid = 1;
System.out.println("Before: arr[mid]=" + arr[mid]);
int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
low++; mid++;
System.out.println("After swap with low: arr[0]=" + arr[0] + ", low=" + low + ", mid=" + mid);
}
}arr = [1, 0, 2]
low, mid = 0, 1
print("Before: arr[mid]=", arr[mid])
arr[low], arr[mid] = arr[mid], arr[low]
low += 1; mid += 1
print(f"After swap with low: arr[0]={arr[0]}, low={low}, mid={mid}")#include <stdio.h>
int main() {
int arr[] = {1, 0, 2};
int low = 0, mid = 1, t;
printf("Before: arr[mid]=%d\n", arr[mid]);
t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
low++; mid++;
printf("After swap with low: arr[0]=%d, low=%d, mid=%d\n", arr[0], low, mid);
return 0;
}Login to try C/C++/Java code in the editor
Handling Two
When mid points to a 2, it's swapped with the element at high, and high moves inward, but mid stays put, because the newly swapped-in value at mid hasn't been checked yet and could be anything.
Example: Handling Two
#include <iostream>
using namespace std;
int main() {
int arr[] = {1, 2, 0};
int mid = 1, high = 2;
cout << "Before: arr[mid]=" << arr[mid] << endl;
swap(arr[mid], arr[high]);
high--;
cout << "After swap with high: arr[mid]=" << arr[mid] << ", mid stays=" << mid << ", high=" << high << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {1, 2, 0};
int mid = 1, high = 2;
System.out.println("Before: arr[mid]=" + arr[mid]);
int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
high--;
System.out.println("After swap with high: arr[mid]=" + arr[mid] + ", mid stays=" + mid + ", high=" + high);
}
}arr = [1, 2, 0]
mid, high = 1, 2
print("Before: arr[mid]=", arr[mid])
arr[mid], arr[high] = arr[high], arr[mid]
high -= 1
print(f"After swap with high: arr[mid]={arr[mid]}, mid stays={mid}, high={high}")#include <stdio.h>
int main() {
int arr[] = {1, 2, 0};
int mid = 1, high = 2, t;
printf("Before: arr[mid]=%d\n", arr[mid]);
t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
high--;
printf("After swap with high: arr[mid]=%d, mid stays=%d, high=%d\n", arr[mid], mid, high);
return 0;
}Login to try C/C++/Java code in the editor
Dutch National Flag Practice
The whole partition finishes in one O(n) pass using only three integer pointers, no extra array, making it a favorite efficient solution for the classic 'sort an array of 0s, 1s, and 2s' problem.
Example: Dutch National Flag Practice
#include <iostream>
using namespace std;
int main() {
int arr[] = {2, 0, 2, 1, 1, 0};
int n = 6, low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
else if (arr[mid] == 1) mid++;
else swap(arr[mid], arr[high--]);
}
cout << "Sorted: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int[] arr = {2, 0, 2, 1, 1, 0};
int low = 0, mid = 0, high = arr.length - 1;
while (mid <= high) {
if (arr[mid] == 0) { int t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
else if (arr[mid] == 1) mid++;
else { int t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
}
System.out.print("Sorted: ");
for (int x : arr) System.out.print(x + " ");
}
}arr = [2, 0, 2, 1, 1, 0]
low, mid, high = 0, 0, len(arr) - 1
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]; low += 1; mid += 1
elif arr[mid] == 1:
mid += 1
else:
arr[mid], arr[high] = arr[high], arr[mid]; high -= 1
print("Sorted:", arr)#include <stdio.h>
int main() {
int arr[] = {2, 0, 2, 1, 1, 0};
int n = 6, low = 0, mid = 0, high = n - 1, t;
while (mid <= high) {
if (arr[mid] == 0) { t=arr[low]; arr[low]=arr[mid]; arr[mid]=t; low++; mid++; }
else if (arr[mid] == 1) mid++;
else { t=arr[mid]; arr[mid]=arr[high]; arr[high]=t; high--; }
}
printf("Sorted: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: