**The Dutch national flag (DNF)** problem is one of the most popular programming problems proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: white, red, and blue. The task is to randomly arrange balls of white, red, and blue such that balls of the same color are placed together.

Consider this problem on an array; the task is to sort arrays of 0, 1, and 2 in linear time without any extra space.
Since the array is only traversed once, the time complexity of the algorithm given below is O(n). 

> Note: this algorithm can be implemented on an array that has three unique elements.

The following illustration shows the algorithm in action:


# Code
In the code below, three indexes are used (i.e., `low`, `high`, `mid`) to sort the input array -- swapping is done according to the above illustration.

// C++ program to sort an array  
#include<bits/stdc++.h>  
using namespace std;  

// Function to sort the input array, 
// the array is assumed  
// to have values in {0, 1, 2}  
void DNFS(int arr[], int arr_size)  
{  
    int low = 0;  
    int high = arr_size - 1;  
    int mid = 0;  
      
    // Iterate till all the elements 
    // are sorted  
    while (mid <= high)  
    {  
        switch (arr[mid])  
        {  
              
            // mid is 0  
        case 0:  
            swap(arr[low++], arr[mid++]);  
            break;  
              
            // mid is 1 .  
        case 1:  
            mid++;  
            break;  
              
            // mid is 2  
        case 2:  
            swap(arr[mid], arr[high--]);  
            break;  
        }  
    }  
}  
  
  
  
// Function to print array arr[]  
void printArray(int arr[], int arr_size)  
{  
    // Iterate and print every element  
    for (int i = 0; i < arr_size; i++)  
        cout << arr[i] << " ";  
  
}  
  
// Driver Code  
int main()  
{  
    int arr[] = {0,0,1,2,0,1,2};  
    int n = sizeof(arr)/sizeof(arr[0]);  

    cout << "Array before running the algorithm: ";  
      
    printArray(arr, n);   
    
    DNFS(arr, n);  
  
    cout << "\nArray after DNFS algorithm: ";  
      
    printArray(arr, n);  
  
    return 0;  
}  

// Java implementation 
import java.io.*; 

class DNF { 

	static void DNFS(int arr[], int arr_size) 
	{ 
		int low = 0; 
		int high = arr_size - 1; 
		int mid = 0, temp=0; // temp variable is used for swapping 
		while (mid <= high) 
		{ 
			switch (arr[mid]) 
			{ 
        case 0: // mid pointer points at 0
        { 
          temp = arr[low]; 
          arr[low] = arr[mid]; 
          arr[mid] = temp; 
          low++; 
          mid++; 
          break; 
        } 
        case 1: // mid pointer points at 1
          mid++; 
          break; 
        case 2: // mid pointer points at 2
        { 
          temp = arr[mid]; 
          arr[mid] = arr[high]; 
          arr[high] = temp; 
          high--; 
          break; 
        } 
			} 
		} 
	} 

	// Function to print array arr[] 
	static void printArray(int arr[], int arr_size) 
	{ 
		int i; 
		for (i = 0; i < arr_size; i++) 
			System.out.print(arr[i]+" "); 
		System.out.println(""); 
	} 

	/*Driver function to check for above functions*/
	public static void main (String[] arguments) 
	{ 
		int arr[] = {0, 0, 1, 2, 0, 1, 2}; 
		int arr_size = arr.length; 
    
    System.out.println("Array before DNFS algorithm"); 
		printArray(arr, arr_size); 
		
    DNFS(arr, arr_size); 
		
    System.out.println("Array after DNFS algorithm"); 
		printArray(arr, arr_size); 
	} 
} 

Java

# Python program to sort an array with 0,1 and 2 in a siingle pass 

# Function to sort array 
def DNFS( arr, arr_size): 
  low = 0
  high = arr_size - 1
  mid = 0
  while mid <= high: 
    if arr[mid] == 0: 
      arr[low],arr[mid] = arr[mid],arr[low] 
      low = low + 1
      mid = mid + 1
    elif arr[mid] == 1: 
      mid = mid + 1
    else: 
      arr[mid],arr[high] = arr[high],arr[mid] 
      high = high - 1
  return arr 
	
# Function to print array 
def printArray(arr): 
	for k in arr: 
		print k, 
	print
	

# Driver Program 
arr = [0, 0, 1, 1, 2, 0, 1, 2] 
arr_size = len(arr)

print "Array before DNFS algorithm", 
printArray(arr) 

arr = DNFS(arr, arr_size) 

print "Array after DNFS algorithm", 
printArray(arr) 

The Dutch national flag problem in C++

Code