Sort an array of 0s, 1s and 2s - Dutch National Flag Problem

Given an array arr[] consisting of only 0s, 1s, and 2s. The objective is to sort the array, i.e., put all 0s first, then all 1s and all 2s in last.

This problem is the same as the famous "Dutch National Flag problem". The problem was proposed by Edsger Dijkstra. The problem is as follows:

Given n balls of colour red, white or blue arranged in a line in random order. You have to arrange all the balls such that the balls with the same colours are adjacent with the order of the balls, with the order of the colours being red, white and blue (i.e., all red coloured balls come first then the white coloured balls and then the blue coloured balls). 

Examples:

Input: arr[] = [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
Explanation: [0, 0, 1, 1, 2, 2] has all 0s first, then all 1s and all 2s in last.

Input: arr[] = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
Explanation: {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2} has all 0s first, then all 1s and all 2s in last.

[Naive Approach] Sorting - O(n × log(n)) Time and O(1) Space

The naive solution is to simply sort the array using a standard sorting algorithm or sort library function. This will simply place all the 0s first, then all 1s and 2s at last.

#include <iostream> #include <vector> #include <algorithm> using namespace std; void sort012(vector<int> &arr) {    // standard sorting function  sort(arr.begin(), arr.end());  } int main() {  vector<int> arr = {0, 1, 2, 0, 1, 2};    sort012(arr);  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << " ";  return 0; } 

import java.util.Arrays; class GfG {  static void sort012(int[] arr) {  // standard sorting function  Arrays.sort(arr);  }  public static void main(String[] args) {  int[] arr = {0, 1, 2, 0, 1, 2};  sort012(arr);  for (int num : arr)  System.out.print(num + " ");  } } 

def sort012(arr): # standard sorting function arr.sort() if __name__ == "__main__": arr = [0, 1, 2, 0, 1, 2] sort012(arr) for num in arr: print(num, end=" ") 

using System; using System.Collections.Generic; class GfG {  static void sort012(List<int> arr) {  // standard sorting function  arr.Sort();  }  static void Main() {  List<int> arr = new List<int> { 0, 1, 2, 0, 1, 2 };  sort012(arr);  foreach (int num in arr)  Console.Write(num + " ");  } } 

function sort012(arr) {  // standard sorting function  arr.sort((a, b) => a - b); } // Driver Code let arr = [0, 1, 2, 0, 1, 2]; sort012(arr); for (let i = 0; i < arr.length; i++) {  console.log(arr[i]); } 

0 0 1 1 2 2 

[Better Approach] Counting 0s, 1s and 2s - Two Pass

A better solution is to traverse the array once and count number of 0s, 1s and 2s, say c0, c1 and c2 respectively. Now traverse the array again, put c0 (count of 0s) 0s first, then c1 1s and finally c2 2s. This solution works in O(n) time, but it is not stable and requires two traversals of the array.

#include <iostream> #include <vector> using namespace std; void sort012(vector<int> &arr) {  int n = arr.size();  int c0 = 0, c1 = 0, c2 = 0;  // count 0s, 1s and 2s  for (int i = 0; i < n; i++) {  if (arr[i] == 0)  c0 += 1;  else if (arr[i] == 1)  c1 += 1;  else  c2 += 1;  }  int idx = 0;    // place all the 0s  for (int i = 0; i < c0; i++)  arr[idx++] = 0;  // place all the 1s  for (int i = 0; i < c1; i++)  arr[idx++] = 1;  // place all the 2s  for (int i = 0; i < c2; i++)  arr[idx++] = 2; } int main() {  vector<int> arr = { 0, 1, 2, 0, 1, 2 };  sort012(arr);  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << " ";  return 0; } 

#include <stdio.h> void sort012(int arr[], int n) {  int c0 = 0, c1 = 0, c2 = 0;  // count 0s, 1s and 2s  for (int i = 0; i < n; i++) {  if (arr[i] == 0)  c0 += 1;  else if (arr[i] == 1)  c1 += 1;  else  c2 += 1;  }  int idx = 0;    // place all the 0s  for (int i = 0; i < c0; i++)  arr[idx++] = 0;  // place all the 1s  for (int i = 0; i < c1; i++)  arr[idx++] = 1;  // place all the 2s  for (int i = 0; i < c2; i++)  arr[idx++] = 2; } 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; } 

class GfG {    static void sort012(int[] arr) {  int n = arr.length;  int c0 = 0, c1 = 0, c2 = 0;  // count 0s, 1s and 2s  for (int i = 0; i < n; i++) {  if (arr[i] == 0)   c0 += 1;  else if (arr[i] == 1)   c1 += 1;  else   c2 += 1;  }  int idx = 0;    // place all the 0s  for (int i = 0; i < c0; i++)  arr[idx++] = 0;  // place all the 1s  for (int i = 0; i < c1; i++)  arr[idx++] = 1;  // place all the 2s  for (int i = 0; i < c2; i++)  arr[idx++] = 2;  }    public static void main(String[] args) {  int[] a = { 0, 1, 2, 0, 1, 2 };  int n = a.length;  sort012(a);  for (int i = 0; i < n; i++)  System.out.print(a[i] + " ");  } } 

def sort012(arr): c0 = 0 c1 = 0 c2 = 0 # count 0s, 1s and 2s for num in arr: if num == 0: c0 += 1 elif num == 1: c1 += 1 else: c2 += 1 idx = 0 # place all the 0s for i in range(c0): arr[idx] = 0 idx += 1 # place all the 1s for i in range(c1): arr[idx] = 1 idx += 1 # place all the 2s for i in range(c2): arr[idx] = 2 idx += 1 if __name__ == "__main__": arr = [0, 1, 2, 0, 1, 2] sort012(arr) for x in arr: print(x, end = " ") 

using System; class GfG {    static void sort012(int[] arr) {  int c0 = 0, c1 = 0, c2 = 0;   // count 0s, 1s and 2s  for (int i = 0; i < arr.Length; i++) {  if (arr[i] == 0)   c0 += 1;  else if (arr[i] == 1)   c1 += 1;  else   c2 += 1;  }  int idx = 0;    // place all the 0s  for (int i = 0; i < c0; i++)  arr[idx++] = 0;  // place all the 1s  for (int i = 0; i < c1; i++)  arr[idx++] = 1;  // place all the 2s  for (int i = 0; i < c2; i++)  arr[idx++] = 2;  }  static void Main() {  int[] arr = { 0, 1, 2, 0, 1, 2 };  sort012(arr);  foreach(int num in arr)  Console.Write(num + " ");  } } 

function sort012(arr) {  let c0 = 0, c1 = 0, c2 = 0;  // count 0s, 1s, and 2s  for (let i = 0; i < arr.length; i++) {  if (arr[i] === 0)   c0 += 1;  else if (arr[i] === 1)   c1 += 1;  else  c2 += 1;  }  let idx = 0;  // place all the 0s  for (let i = 0; i < c0; i++)   arr[idx++] = 0;  // place all the 1s  for (let i = 0; i < c1; i++)   arr[idx++] = 1;  // place all the 2s  for (let i = 0; i < c2; i++)   arr[idx++] = 2; } // Driver Code let arr = [0, 1, 2, 0, 1, 2]; sort012(arr); console.log(arr.join(' ')); 

0 0 1 1 2 2 

Time Complexity: O(2 × n), where n is the number of elements in the array
Auxiliary Space: O(1)

The issues with this approach are:

• It would not work if 0s and 1s represent keys of objects.
• Not stable
• Requires two traversals

[Expected Approach] 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 4 parts -

• arr[0 .. lo - 1] → All 0s
• arr[lo .. mid - 1] → All 1s
• arr[mid .. hi] → Unprocessed elements (unknown)
• arr[hi + 1 .. n - 1] → All 2s

Here,

• lo is the index where the next 0 should be placed,
• mid is the current element being checked,
• hi is the index where the next 2 should be placed.

Working:

#include <iostream> #include <vector> using namespace std; void sort012(vector<int> &arr) {  int n = arr.size();    // initialize three pointers:  // lo: boundary for 0s  // mid: current element being checked  // hi: boundary for 2s  int lo = 0;  int hi = n - 1;  int mid = 0;    // process elements until mid crosses hi  while (mid <= hi) {  if (arr[mid] == 0) {    // current is 0: swap with lo and move both   // pointers forward  swap(arr[lo++], arr[mid++]);  }  else if (arr[mid] == 1) {  // current is 1: it's already in correct position  mid++;  }  else {  // current is 2: swap with hi and move hi backward  // do not increment mid, as swapped value needs  // to be re-checked  swap(arr[mid], arr[hi--]);  }  } } int main() {  vector<int> arr = { 0, 1, 2, 0, 1, 2 };  int n = arr.size();    // sort the array in-place  sort012(arr);   for (int i = 0; i < n; i++)  cout << arr[i] << " ";  return 0; } 

#include <stdio.h> // Function to sort array containing 0s, 1s, and 2s void sort012(int arr[], int n) {    // initialize three pointers:  // lo: boundary for 0s  // mid: current element being checked  // hi: boundary for 2s  int lo = 0;  int hi = n - 1;  int mid = 0;  // process elements until mid crosses hi  while (mid <= hi) {  if (arr[mid] == 0) {    // current is 0: swap with lo and move both   // pointers forward  int temp = arr[lo];  arr[lo++] = arr[mid];  arr[mid++] = temp;  }  else if (arr[mid] == 1) {  // current is 1: it's already in correct position  mid++;  }  else {  // current is 2: swap with hi and move hi backward  // do not increment mid, as swapped value needs  // to be re-checked  int temp = arr[mid];  arr[mid] = arr[hi];  arr[hi--] = temp;  }  } } int main() {  int arr[] = {0, 1, 2, 0, 1, 2};  int n = sizeof(arr) / sizeof(arr[0]);  // sort the array in-place  sort012(arr, n);  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  return 0; } 

import java.util.*; class GfG {  static void sort012(int[] arr) {  int n = arr.length;    // initialize three pointers:  // lo: boundary for 0s  // mid: current element being checked  // hi: boundary for 2s  int lo = 0;  int hi = n - 1;  int mid = 0;    // process elements until mid crosses hi  while (mid <= hi) {  if (arr[mid] == 0) {    // current is 0: swap with lo and move both   // pointers forward  int temp = arr[lo];  arr[lo++] = arr[mid];  arr[mid++] = temp;  }  else if (arr[mid] == 1) {  // current is 1: it's already in correct position  mid++;  }  else {  // current is 2: swap with hi and move hi backward  // do not increment mid, as swapped value needs  // to be re-checked  int temp = arr[mid];  arr[mid] = arr[hi];  arr[hi--] = temp;  }  }  }  public static void main(String[] args) {  int[] arr = { 0, 1, 2, 0, 1, 2 };  int n = arr.length;  // sort the array in-place  sort012(arr);  for (int i = 0; i < n; i++)  System.out.print(arr[i] + " ");  } } 

def sort012(arr): n = len(arr) # initialize three pointers: # lo: boundary for 0s # mid: current element being checked # hi: boundary for 2s lo = 0 hi = n - 1 mid = 0 # process elements until mid crosses hi while mid <= hi: if arr[mid] == 0: # current is 0: swap with lo and move both  # pointers forward arr[lo], arr[mid] = arr[mid], arr[lo] lo += 1 mid += 1 elif arr[mid] == 1: # current is 1: it's already in correct position mid += 1 else: # current is 2: swap with hi and move hi backward # do not increment mid, as swapped value needs # to be re-checked arr[mid], arr[hi] = arr[hi], arr[mid] hi -= 1 if __name__ == "__main__": arr = [0, 1, 2, 0, 1, 2] n = len(arr) # sort the array in-place sort012(arr) for i in range(n): print(arr[i], end=' ') 

using System; class GfG {  static void sort012(int[] arr) {  int n = arr.Length;  // initialize three pointers:  // lo: boundary for 0s  // mid: current element being checked  // hi: boundary for 2s  int lo = 0;  int hi = n - 1;  int mid = 0;  // process elements until mid crosses hi  while (mid <= hi) {  if (arr[mid] == 0) {  // current is 0: swap with lo and move both   // pointers forward  int temp = arr[lo];  arr[lo++] = arr[mid];  arr[mid++] = temp;  }  else if (arr[mid] == 1) {  // current is 1: it's already in correct position  mid++;  }  else {  // current is 2: swap with hi and move hi backward  // do not increment mid, as swapped value needs  // to be re-checked  int temp = arr[mid];  arr[mid] = arr[hi];  arr[hi--] = temp;  }  }  }  static void Main() {  int[] arr = { 0, 1, 2, 0, 1, 2 };  int n = arr.Length;  // sort the array in-place  sort012(arr);  for (int i = 0; i < n; i++)  Console.Write(arr[i] + " ");  } } 

function sort012(arr) {  let n = arr.length;    // initialize three pointers:  // lo: boundary for 0s  // mid: current element being checked  // hi: boundary for 2s  let lo = 0;  let hi = n - 1;  let mid = 0;    // process elements until mid crosses hi  while (mid <= hi) {  if (arr[mid] === 0) {    // current is 0: swap with lo and move both   // pointers forward  [arr[lo], arr[mid]] = [arr[mid], arr[lo]];  lo++;  mid++;  }  else if (arr[mid] === 1) {  // current is 1: it's already in correct position  mid++;  }  else {  // current is 2: swap with hi and move hi backward  // do not increment mid, as swapped value needs  // to be re-checked  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];  hi--;  }  } } // Driver Code let arr = [0, 1, 2, 0, 1, 2]; let n = arr.length; // sort the array in-place sort012(arr); for (let i = 0; i < n; i++)  process.stdout.write(arr[i] + " "); 

0 0 1 1 2 2