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 <stdio.h>

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++) printf("%d ", arr[i]);
    printf("\n");
}

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

Output:

Rearranged Array:
0 0 0 1 1 1 2 2
            

Method 2: Dutch National Flag Algorithm

#include <stdio.h>

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

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

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

Output:

Rearranged Array:
0 0 1 1 2 2
            

Method 3: Using Extra Space

#include <stdio.h>

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++) printf("%d ", arr[i]);
    printf("\n");
}

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

Output:

Rearranged Array:
0 0 1 1 1 2 2