# Sort an array of 0s,1s,2s

You are given an array of 0s 1s and 2s in random order. Sort the array so the o,1 and 2 are segregated.

This problem is similar to Dutch national Flag problem.

Method 1:
Use count sort logic.

```void sort012(int *a, int n){
int i,j,k;
int count[2]={0};
for(i=0;i< n;i++)
{
if(a[i]==0)
count[a[i]]++;
else if(a[i]==1)
count[a[i]]++;
else if(a[i]==2)
count[a[i]]++;

}

for(i=0;i < count[0];i++)
a[i]=0;
for(j=i;j < i+count[1];j++)
a[j]=1;
for(k=j;k < j+count[2];k++)
a[k]=2;

for(i=0;i<n;i++)
printf("%d",a[i]);

}
```

Complexity: O(N)

Method 2:
1. Sort the array treating {0} as one group and {1, 2} as one group.
2. Now again sort the array of 1 & 2.

```void swap(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

void sort012(int *a, int n)
{
i = 0;
j = n-1;

// first loop sorts the array with 0 at front and {1, 2} at end
while (i <=j) {
while (a[i] ==0) {
i++;
}
while (a[j] == 1 || a[j] == 2) {
j--;
}
swap(a,i,j);
}

// This loop sorts array of 1 & 2
i = j;
j = n-1;
while (i <=j) {
while (a[i] ==1) {
i++;
}
while (a[j] == 2) {
j--;
}
swap(a,i,j);
}
}
```

Complexity: O(N)

Method 3:
Only traversing the array once.

```void sort012(int[] a){
int low = -1;
int mid = 0;
int high = a.length;

while(mid < high){
if(a[mid] == 0){
low++;
swap(a, low, mid);
mid++;
}else if(a[mid] == 1){
mid++;
}else if(a[mid] == 2){
high--;
swap(a, mid, high);
}
}
}
```

Complexity: O(N)
In this method, we traversed the array once.

### 3 Thoughts on “Sort an array of 0s,1s,2s”

1. https://oj.leetcode.com/problems/sort-colors/

void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void sortColors(int A[], int n) {
int hi=n-1;
int lo=0;
int mid=0;
while(mid<=hi)
{switch(A[mid])
{
case 0:swap(&A[mid++],&A[lo++]);
break;
case 1:mid++;
break;
case 2:swap(&A[mid],&A[hi--]);
break;
}
}
}

2. bugeater on October 2, 2014 at 12:37 am said:

https://oj.leetcode.com/problems/sort-colors/

void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void sortColors(int A[], int n) {
int hi=n-1;
int lo=0;
int mid=0;
while(mid<=hi)
{switch(A[mid])
{
case 0:swap(&A[mid++],&A[lo++]);
break;
case 1:mid++;
break;
case 2:swap(&A[mid],&A[hi--]);
break;
}
}
}

3. Deathrace on March 2, 2015 at 12:08 am said:

Given Method 2 does not work. It goes into infinite loop.