Considering an array arr[] that only contains 0s, 1s, and 2s. Sorting the array means placing all 0s first, followed by all 1s and all 2s last.
This issue is identical to the well-known “Dutch National Flag problem.” Edsger Dijkstra was the one who introduced the problem. The following is the issue:
Given a line of n balls in a random arrangement, they can be red, white, or blue. All of the balls must be arranged so that they are adjacent to each other in the same color order, which is red, white, and blue (that is, all red balls should be placed first, followed by white balls, and finally blue balls).
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.Table of Content
- [Naive Approach] Sorting – O(n * log(n)) Time and O(1) Space
- [Better Approach] Counting 0s, 1s and 2s – Two Pass – O(n) Time and O(1) Space
- [Expected Approach] Dutch National Flag Algorithm – One Pass – O(n) Time and O(1) Space
[Naive Approach] Sorting – O(n * log(n)) Time and O(1) Space
Sorting the array with a conventional sorting algorithm or sort library function is the naïve option. This will merely arrange all of the zeros first, followed by all of the ones and twos last. This method uses O(1) space and O(n * log(n)) time.
[Better Approach] Counting 0s, 1s and 2s – Two Pass – O(n) Time and O(1) Space
Counting the number of 0s, 1s, and 2s—let’s say c0, c1, and c2—after one traversal of the array is a superior method. Go through the array once again now, entering c0 (count of 0s) 0s first, followed by c1 1s and c2 2s. Although this method is unstable and necessitates two array traversals, it operates in O(n) time.
C++
// C++ Program to sort an array of 0s, 1s and 2s
// by counting the occurrence of 0s, 1s and 2s
#include <iostream>
#include <vector>
using namespace std;
// Function to sort the array of 0s, 1s and 2s
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;
}C
// C Program to sort an array of 0s, 1s and 2s
// by counting the occurrence of 0s, 1s and 2s
#include <stdio.h>
// Function to sort the array of 0s, 1s and 2s
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;
}Python
# Python Program to sort an array of 0s, 1s and 2s
# by counting the occurrence of 0s, 1s and 2s
# Function to sort an array of 0s, 1s and 2s
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
arr = [0, 1, 2, 0, 1, 2]
sort012(arr)
for x in arr:
print(x, end = " ")C#
// C# Program to sort an array of 0s, 1s and 2s
// by counting the occurrence of 0s, 1s and 2s
using System;
class GfG {
// Function to sort the array of 0s, 1s and 2s
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 + " ");
}
}JavaScript
// JavaScript Program to sort an array of 0s, 1s and 2s
// by counting the occurrence of 0s, 1s and 2s
// Function to sort an array of 0s, 1s and 2s
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;
}
let arr = [0, 1, 2, 0, 1, 2];
sort012(arr);
console.log(arr.join(' '));Output
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