Sorting Array of 0’s and 1’s

Posted by

4


You are given an Array of N size. It contains 0 and 1 only. You have to arrange all 0s before all 1s (In the program you can’t travel more than once. Minimum complexity desired).

Idea : Move a pointer left, from the front, until it encounters a 1
Move a pointer right, from the end, until it encounters a 0
Swap the elements at the two pointers (if they haven’t crossed)
Repeat this for entire array – this is inplace and single pass.

Code :

public class swap01
{
    public static void main(String arg[])
    {
        int[] a = {0,1,1,0,0,1,1,1,0};
        int l =0;
        int r= a.length-1;
        while(l<r)
        {
            if(a[l] == 0)
            {
                l++;
            }
            else if(a[r] == 1)
            {
                r–;
            }
            else {
                swap(a,l,r);
                l++;
                r–;
            }
        }
        for(int i=0;i<a.length;i++)
            System.out.print(a[i] + ",");
    }
    private static void swap(int[] a, int l, int r)
    {
        int tmp = a[l];
        a[l] = a[r];
        a[r]=tmp;
    }
}

4 thoughts on “Sorting Array of 0’s and 1’s”

  1. Good one. I gave a stupid counting sort example as an answer when asked in Amazon interview 😦
    Wish I had known this approach. Interviewer kept asking for a better approach.

    int a[]={1,1,0,0,1,1,1,0,1,0};
    int length=sizeof(a)/sizeof(a[0]);
    int count[2]={0,0};

    for(i=0;i<length;i++)
    {
    //Important to understand this
    count[a[i]]++;
    }

    for(i=0;i<count[0];i++)
    a[i]=0;
    for(j=count[0];j<count[0]+count[1];j++)
    a[j]=1;
    //printf("Count %d %d\n",count[0],count[1]);

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

    Reply

  2. Technically your solution runs in 3n time (1 for read and 2 for swapping).
    If u just count the 0’s in first run and rewrite the array in second, it’ll only take 2n

    int i, ;count0 = 0;
    for(i=0; i<n; i++){ if(a[i]==0) count0++; }
    for(i=0; i<count0; i++) a[i]=0;
    for(i=count0; i<n; i++) a[i]=1;

    Reply

Leave a comment