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.

Source : http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation