Rearrange 0s, 1s, and 2s without Sorting

Understanding the Problem

The goal is to rearrange an array containing 0s, 1s, and 2s without using any sorting algorithm.

We will explore three different methods to achieve this in C++.

Method 1: Counting Approach

#include <iostream>
using namespace std;

void rearrange(int arr[], int n) {
    int count0 = 0, count1 = 0, count2 = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == 0) count0++;
        else if (arr[i] == 1) count1++;
        else count2++;
    }
    for (int i = 0; i < count0; i++) arr[i] = 0;
    for (int i = count0; i < count0 + count1; i++) arr[i] = 1;
    for (int i = count0 + count1; i < n; i++) arr[i] = 2;
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {0, 1, 2, 1, 0, 2, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrange(arr, n);
    cout << "Rearranged Array:" << endl;
    printArray(arr, n);
    return 0;
}
            

Output:

Rearranged Array:
0 0 0 1 1 1 2 2
            

Method 2: Dutch National Flag Algorithm

#include <iostream>
using namespace std;

void rearrange(int arr[], int n) {
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] == 0) {
            swap(arr[low], arr[mid]);
            low++; mid++;
        } else if (arr[mid] == 1) {
            mid++;
        } else {
            swap(arr[mid], arr[high]);
            high--;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrange(arr, n);
    cout << "Rearranged Array:" << endl;
    printArray(arr, n);
    return 0;
}
            

Output:

Rearranged Array:
0 0 1 1 2 2
            

Method 3: Using Extra Space

#include <iostream>
using namespace std;

void rearrange(int arr[], int n) {
    int temp[n], index = 0;
    for (int i = 0; i < n; i++) if (arr[i] == 0) temp[index++] = 0;
    for (int i = 0; i < n; i++) if (arr[i] == 1) temp[index++] = 1;
    for (int i = 0; i < n; i++) if (arr[i] == 2) temp[index++] = 2;
    for (int i = 0; i < n; i++) arr[i] = temp[i];
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {1, 0, 2, 1, 0, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrange(arr, n);
    cout << "Rearranged Array:" << endl;
    printArray(arr, n);
    return 0;
}
            

Output:

Rearranged Array:
0 0 1 1 1 2 2