Dutch National Flag Algorithm – One Pass – O(n) Time and O(1) Space

The problem is similar to “Segregate 0s and 1s in an array”. The idea is to sort the array of size n using three pointers: lo = 0, mid = 0 and hi = n – 1 such that the array is divided into three parts –


arr[0] to arr[lo – 1]: This part will have all the zeros.
arr[lo] to arr[mid – 1]: This part will have all the ones.
arr[hi + 1] to arr[n – 1]: This part will have all the twos.
Here, lo indicates the position where next 0 should be placed, mid is used to traverse through the array and hi indicates the position where next 2 should be placed.

Navigate through the array until mid <= hi. Three scenarios can be identified based on the value of arr[mid]:

• Since all of the zeros are up to index lo-1, switch arr[lo] and arr[mid] and increase lo by 1 before moving on to the next element with an increment of 1.
• Proceed to the following element to increase mid by 1 after arr[mid] = 1.
• Since all of the twos are from index hi + 1 to n – 1, switch arr[mid] and arr[hi] and decrement hi by 1. The element that is currently at index mid may be a 0, thus it needs to be verified again, so we don’t go on to the next element.

C++

// C++ program to sort an array of 0s, 1s and 2s 
// using Dutch National Flag Algorithm

#include <iostream>
#include <vector>
using namespace std;

// Function to sort an array of 0s, 1s and 2s
void sort012(vector<int> &arr) {
    int n = arr.size();
    int lo = 0;
    int hi = n - 1;
    int mid = 0;

    // Iterate till all the elements
    // are sorted
    while (mid <= hi) {
        if (arr[mid] == 0)
            swap(arr[lo++], arr[mid++]);
        else if (arr[mid] == 1)
            mid++;
        else
            swap(arr[mid], arr[hi--]);
    }
}

int main() {
    vector<int> arr = { 0, 1, 2, 0, 1, 2 };
    int n = arr.size();

    sort012(arr);

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

C

// C program to sort an array of 0s, 1s and 2s 
// using Dutch National Flag Algorithm

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to sort an array of 0s, 1s and 2s
void sort012(int arr[], int n) {
    int lo = 0;
    int hi = n - 1;
    int mid = 0;

    // Iterate till all the elements
    // are sorted
    while (mid <= hi) {
        if (arr[mid] == 0)
            swap(&arr[lo++], &arr[mid++]);
        else if (arr[mid] == 1)
            mid++;
        else
            swap(&arr[mid], &arr[hi--]);
    }
}

int main() {
    int arr[] = { 0, 1, 2, 0, 1, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort012(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Java

// Java program to sort an array of 0s, 1s and 2s 
// using Dutch National Flag Algorithm

import java.util.ArrayList;
import java.util.Arrays;
class GfG {

    // Function to sort an array of 0s, 1s and 2s
    static void sort012(int[] arr) {
        int n = arr.length;
        int lo = 0;
        int hi = n - 1;
        int mid = 0, temp = 0;

        // Iterate till all the elements are sorted
        while (mid <= hi) {
            if (arr[mid] == 0) {
                swap(arr, mid, lo);
                lo++;
                mid++;
            }
            else if (arr[mid] == 1) {
                mid++;
            }
            else {
                swap(arr, mid, hi);
                hi--;
            }
        }
    }
    
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 0, 1, 2 };
        sort012(arr);

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }
}

Python

# Python program to sort an array of 0s, 1s and 2s 
# using Dutch National Flag Algorithm

# Function to sort an array of 0s, 1s and 2s
def sort012(arr):
    n = len(arr)
    lo = 0
    hi = n - 1
    mid = 0

    # Iterate till all the elements are sorted
    while mid <= hi:
      if arr[mid] == 0:
        arr[lo], arr[mid] = arr[mid], arr[lo]
        lo = lo + 1
        mid = mid + 1
        
      elif arr[mid] == 1:
        mid = mid + 1
        
      else:
        arr[mid], arr[hi] = arr[hi], arr[mid]
        hi = hi - 1
        
    return arr

arr = [0, 1, 2, 0, 1, 2]
arr = sort012(arr)

for x in arr:
    print(x, end=" ")

C#

// C# program to sort an array of 0s, 1s and 2s 
// using Dutch National Flag Algorithm

using System;

class GfG {

    // Function to sort an array of 0s, 1s and 2s
    static void sort012(int[] arr) {
        int n = arr.Length;
        int lo = 0;
        int hi = n - 1;
        int mid = 0;

        // Iterate till all the elements
        // are sorted
        while (mid <= hi) {
            if (arr[mid] == 0) {
                swap(arr, lo, mid);
                lo++;
                mid++;
            }
            else if (arr[mid] == 1) {
                mid++;
            }
            else {
                swap(arr, mid, hi);
                hi--;
            }
        }
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void Main() {
        int[] arr = { 0, 1, 2, 0, 1, 2 };
        sort012(arr);

        foreach(int num in arr) Console.Write(num + " ");
    }
}

JavaScript

// JavaScript program to sort an array of 0s, 1s and 2s 
// using Dutch National Flag Algorithm

// Function to sort an array of 0s, 1s and 2s
function sort012(arr) {
    let lo = 0;
    let hi = arr.length - 1;
    let mid = 0;

    // Iterate till all the elements are sorted
    while (mid <= hi) {
            if(arr[mid] === 0) {
            [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
            lo++;
            mid++;
         }
         else if(arr[mid] === 1) {
             mid++;
         }
         else {
            [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
            hi--;
         }
    }
}

let arr = [0, 1, 2, 0, 1, 2];
sort012(arr);
console.log(arr.join(' '));

Output

0 0 1 1 2 2