# How to Sort an array of 0s, 1s and 2s?

## Problem:

Given an array of size N containing only 0s, 1s, and 2s; sort the array in ascending order.

### Example 1:

Input:

N = 5
arr[]= {0 2 1 2 0}

Output:

0 0 1 2 2

Explanation:

0s 1s and 2s are segregated
into ascending order.

### Example 2:

Input:

N = 3
arr[] = {0 1 0}

Output:

0 0 1

Explanation:

0s 1s and 2s are segregated
into ascending order.

You don’t need to read input or print anything. Your task is to complete the function sort012() that takes an array arr and N as input parameters and sorts the array in-place.

Expected Time Complexity: O(N)

Expected Auxiliary Space: O(1)

## Solution

### Java Code:

```// Java program to sort an array of 0, 1 and 2
import java.io.*;

class countzot {

// Sort the input array, the array is assumed to
// have values in {0, 1, 2}
static void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0, temp = 0;
while (mid <= hi) {
switch (a[mid]) {
case 0: {
temp = a[lo];
a[lo] = a[mid];
a[mid] = temp;
lo++;
mid++;
break;
}
case 1:
mid++;
break;
case 2: {
temp = a[mid];
a[mid] = a[hi];
a[hi] = temp;
hi--;
break;
}
}
}
}

/* Utility function to print array arr[] */
static void printArray(int arr[], int arr_size)
{
int i;
for (i = 0; i < arr_size; i++)
System.out.print(arr[i] + " ");
System.out.println("");
}

/*Driver function to check for above functions*/
public static void main(String[] args)
{
int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
int arr_size = arr.length;
sort012(arr, arr_size);
System.out.println("Array after segregation ");
printArray(arr, arr_size);
}
}
```

### C++ Code:

```// C++ program to sort an array
// with 0, 1 and 2 in a single pass
#include <bits/stdc++.h>
using namespace std;

// Function to sort the input array,
// the array is assumed
// to have values in {0, 1, 2}
void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;

// Iterate till all the elements
// are sorted
while (mid <= hi) {
switch (a[mid]) {

// If the element is 0
case 0:
swap(a[lo++], a[mid++]);
break;

// If the element is 1 .
case 1:
mid++;
break;

// If the element is 2
case 2:
swap(a[mid], a[hi--]);
break;
}
}
}

// Function to print array arr[]
void printArray(int arr[], int arr_size)
{
// Iterate and print every element
for (int i = 0; i < arr_size; i++)
cout << arr[i] << " ";
}

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

sort012(arr, n);

cout << "array after segregation ";

printArray(arr, n);

return 0;
}

```