Sorting Array of 0's and 1's

http://techpuzzl.wordpress.com/2010/01/10/sorting-array-of-0s-and-1s/

 

Technology, Puzzles, everything you want for an interview.

Sorting Array of 0’s and 1’s

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;
    }
}

 

---

The information contained in this message may be confidential and legally protected under applicable law. The message is intended solely for the addressee(s). If you are not the intended recipient, you are hereby notified that any use, forwarding, dissemination, or reproduction of this message is strictly prohibited and may be unlawful. If you are not the intended recipient, please contact the sender by return e-mail and destroy all copies of the original message.