CareerCup

I answered Bucket sort or quick sort are the best for this prob. Any suggestions?? Is there a better algo for this problem?

If there are only two type elements(0/1) then go through all the elements, maintain two counters which would count # of 0's and 1's. Finally replace the whole array with x # of 0's and then y # of 1's.

This algo would take O(2n)=O(n) steps

Hope this link help. It has the implementation for both with counter and quick sort.

http://mganesh.blogspot.com/2009/01/arrange-0-1.html

@Prince ==> your method will have the complexity of O(4n). See the above link for reference.

oh yaar its simple count the number of times loop went and count number of ones in that loop. number of zeros = loop count - 1 count. either regenerate it during counting.

You just need to apply counting sort which would take O(2+n)steps.
Prince is correct!

Prince sol is nice using bucket , but same can be done using less no of insertion and deletion just start two counter one from start and one from end,keep on incrementing start till 1 encountered by start counter and 0 encountered by end counter then swap them . stop doing this when start is grater then end.

Start from both ends of the array, swap 0s and 1s as required

If there are only two type elements(0/1) then we can also use counting sort. It has an advantage of being a stable sort and runs in O(n+k), where k is the range of numbers, in this case k = 2.

Dumbo is correct ......though it is not a stable sort (we do not need one here :-) )....

does the work in O(n) and no extra space .

sortArraysOfOnesAndZeros(int[] a, int n)
{
int start = 0;
int end = n-1;
while(end > start)
{
if(a[start] > a[end])
{
swap(a[start], a[end];
}
else if(a[start] == a[end] == 0)
{
start++;
continue;
}
else if(a[start] == a[end] == 1)
{
end--;
continue;
}
start++; end--;
}

Complexity is O(n).

public static void SortZeroAndOne(int[] arr, int n)
        {
            int i=0,j=n-1;
            while (i < j)
            {
             
                if (arr[i] == 1)
                {
                    while (arr[j] != 0&& i < j)
                    {
                        j--;
                    }
               if(i==j) break;
                    if (arr[i] != arr[j] )
                    {
                        int temp = arr[j];
                        arr[j] = arr[i];
                        arr[i] = temp;
                    }
                }
                ++i;
            }
        }