CareerCup

void sort(int * a,int len)
{
int i= 0, j = len;
while(j>i){
if(a[i] == 0){
i++;
continue;
}
while((a[--j] == 1)&&j>=0);
if(j>i)
SWAP(a[i],a[j]);
}
}

Go Through the array and count number of zeros(say it countZeros). Now go through again and set it to zero till index countZeros-1. remaining array should be 1.
TC O(n)
space complexity : constant

/* Returns 1 if successful, 0 otherwise */
int sort01( int * a, int n )
{
    int i, j, temp;
    i = j = 0;
    if ( !a ) {
        printf("Invalid array parameter\n");
        return 0;
    }
    if ( n < 0 ) {
        printf("Invalid array size\n");
        return 0;
    }
    while ( j < n ) {
        if ( 0 == a[j] ) {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
            ++i;
        }
        ++j;
    }
    return 1;
}

1. Time complexity O(N)
2. Space complexity O(1)
3. Tested code till n = 50 million, results correctly in less than 1 second
4. Single pass algorithm
5. Clean and solid

private static void SortZerosAndOnes(int[] array, int size) {
    int low = 0; int high = size-1;
    while(low < high) {
        if (array[low] == 0) {
            low++;
            continue;
        }
        if (array[high] == 1) {
            high--;
            continue;
        }
        // now array[low] == 1 and array[high] == 0, change them and move both pointers
        array[low] = 0; array[high] = 1; low++; high--;
    }
}

Note: you can eliminate the size parameter and use array.length-1 as the initial value for high

you can use BitVector

void sort(int arr[], int size)
{
	int begin = 0;
	int end = size;	
	while(begin < end)
	{
		while(arr[begin] == 0)
		{
			begin++;			
		}

		while(arr[end] == 1)
		{
			end--;			
		}
		
		if(begin < end)
		{
			int temp = arr[begin];
			arr[begin] = arr[end];
			arr[end] = temp;	
		}
	}
}

void sort(int arr[], int size)
{
	int begin = 0;
	int end = size;	
	while(begin < end)
	{
		while(arr[begin] == 0)
		{
			begin++;			
		}

		while(arr[end] == 1)
		{
			end--;			
		}
		
		if(begin < end)
		{
			int temp = arr[begin];
			arr[begin] = arr[end];
			arr[end] = temp;	
		}
	}
}

What is the complexity? O(n)

Hi all
Can any 1 will tell wt is prblm with this logic as it is simple n clean solution
============================================================
Go Through the array and count number of zeros(say it countZeros). Now go through again and set it to zero till index countZeros-1. remaining array should be 1.
TC O(n)
space complexity : constant

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 0;
            int[] numbers = { 1, 0, 1, 0, 1, 0, 0, 1,0, 1, 0, 1 };
            foreach (int num in numbers)
            {
                if (num == 0)
                    count++;
            }
            for (int i = 0; i < numbers.Length; i++)
            {
                if (i <= count)
                {
                    numbers[i] = 0;
                }
                else
                    numbers[i] = 1;
            }

            foreach (int num in numbers)
                System.Console.WriteLine(num);

            System.Console.Read();


        }
        
    }
}

ha ha ha much simplier. count all the ones and all the zeros and then re-construct with the zeros first and then the ones.

count0=0;
count1=0;
for(i=0; i< tab.length ; i++)
  if(tab[i]=='0') count0++;
  else count1++;
for(i=0; i<count0; i++) tab[i]='0';
for(j=0; j<count1; j++) tab[i+j]='1';

Sort in-place and wo additional storage. For the sake of brevity, some checkings are omitted.

void sort_zeros_n_ones(int dat[], int count)
{
    int s, e;
    
    s = 0;
    e = count - 1;
    
    /* We want values to be sorted in ascending order, i.e. like "000..11..1" */
    while (s < e) {
        while(dat[s] == 0) {
            s++;
        }        
        while(dat[e] == 1) {
            e--;
        }
        
        if (s < e) {
            swap(dat, s, e);
            s++;
            e--;
        }
    }
}

i guess this works for above criteria....

for( i = 0; i<n/2; i++){
if( a[i] < a[n-i-1]){
temp = a[i];
a[i] = a [n-i-1];
a[n-i-1] = temp;
}
}

The interviewer seems to have given you more than enough hints about what algorithm to use:

The obvious answer is "Counting sort" because...
1) According to the interviewer, he gave you hints saying that the input will be in the range of 0-100 which means that you can just maintain 100 counters for sorting.
2) Time complexity of this algorithm is O(n) and space complexity is O(k) where n is the number of elements in the input array and k is the number of "distinct" elements in the array (which is 100 in this case).

PS: I don't mean to be rude but before rubbishing this comment, plz go through the counting sort algorithm once and then give you're feedback. :) :)

import com.sun.org.apache.bcel.internal.generic.SWAP;


public class question {

	public static void main(String[] args) {

		int [] arr = new int[30];
		for (int i = 0; i < arr.length; i++) {
			arr[i]= (int)(Math.random()*2);
			System.out.print("  "+ arr[i]);
		}
		System.out.println(" ");
		int i=0,j=29;
		while(i<j){

			for(;i < arr.length; i++) {
				if(arr[i]>0){
					System.out.println(" i " + i);
					break;
				}
			}
			for(;j>0; j--) {
				if(arr[j]<1){
					System.out.println(" j " + j);
					break;
				}
			}
			if(i>j){
				break;
			}else{
				swap(arr,i,j);
			}


		}
		System.out.println(" ");
		System.out.println(" output------>");
		for ( i = 0; i < arr.length; i++) {
			System.out.print("  "+ arr[i]);
		}

	}

	private static void swap(int[] arr, int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;

	}
}

I think the time complexity is o(n)
and space complexity is constant

}

for(int i= 0;i<n; i++)
    {
        if(array[i] == 0){
             counter0++;           //this variable is used to count no of zeros
          }
        else
             counter1++;           //this variable is used to count no of ones
    }
for(int i=0; i<counter0;i++)
   {
      array[i]=0;
  }
for(int i= counter0 ; i<n; i++)
    {
       array[i]=1;
     }