CareerCup

i = 0;
j = n-1;

while( i < j){

while( array[i] == 0 && i < j )
i++;

while( array[j] == 1 && j > i )
j--;

if ( i < j )
swap( a[i], a[j] );

}

This is O(n) solution

int i=0,j=n-1;

while(i<=j)
{
if(arr[i]==0)
i++;
if(arr[j]==1)
j--;
if(arr[i]==1 && arr[j]==0)
{
arr[i++]=0;
arr[j--]=1;
}
}

@ "quicksort; O(lg N)". Huh?

Just count and you are done. O(N)

btw, what does 'most efficient' mean?

google for "2 color sort problem"

just count the number of 0 and 1 in the array. then again write the number of 0/1 in the array as per there count back to the array.

Simple. Check this coe.

int a[]={1,1,0,0,1,1,1,0,1,0};
int length=sizeof(a)/sizeof(a[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]);

forgot to initialize count[]
int count[2]={0,0};

topcoder's solution is the best....since it is O(n) and sorts in a single scan of array

function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex


Reference: From wiki


Following algorithm has time complexity O(n).
It can used for above problem with pivote element as 1.
But, this algorithm is not stable.

Hop, question does not asking stable algorithm!

Rachit got the best answer -- short and sweet. Lemme encode it as a function in Python:

def sort01(array):
s = sum(array)
return (len(array)-s)*[0] + s*[1]

There is still more efficient solution exists.
Its O(N) but more cache-efficient.
think about it. (just one 'for' loop)

max = array.length();
min = 0;
for(int bit : array){
if(bit ==1)
newArray[max--] = 1;
else newArray[min++] = 0;
}

max = array.length();
min = 0;
for(int bit : array){
if(bit ==1)
newArray[max--] = 1;
else newArray[min++] = 0;
}

How about this :
h ttp://techpuzzl.wordpress.com/2010/01/10/sorting-array-of-0s-and-1s/

What happens when I also put 2 inside the array and now sort 0,1,2?

int i=0, j=n-1, temp; // n is size of array

while(j>=i)
{
if (a[i]==1 && a[j]==0)
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}

if (a[i]!=1)
i++;

if (a[j]!=0)
j--;
}

int i=0, j=n-1, temp; // n is size of array

while(j>=i)
{
if (a[i]==1 && a[j]==0)
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}

if (a[i]!=1)
i++;

if (a[j]!=0)
j--;
}

my solution O(n)... no swapping
--------
the main loop

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

Do you really need to swap the variables? Try the boolean NOT operator. Topcoder's solution is a good one.

Here's a slight variation:
i = 0;
j = n-1;

while( i < j){

while( !array[i] && i < j ) i++;

while( array[j] && j > i ) j--;

if ( i < j )
a[j]=1;
a[i]=0;

}

Since it has just 0 and 1 add all the array elements in first pass. The sum gives the number of 1s. Now, just populate the array in the second pass with that many 1s and 0s. Obviously start with populating 0s and then populate 1s.

1. Iterate once in a single pass and count number of 0s and 1s
2. Iterate once again and fill 0s and 1s

Complexity : O(n)

for(i=0,j=9;i<j;){
                swap=0;
                if(a[i]==1){
                        swap=1;
                }
                else{
                        i++;
                }
                if(a[j]==0){
                        swap=1;
                }
                else{
                        j--;
                }

                if(swap)
                {
                        a[i]=!a[i];
                        a[j]=!a[j];
                }
        }

Solution using one for loop -
int[] a = {0,1,1,0,0,1,1,0,0,1};
int no = a.length;
int[] b = new int[no];
int zcount = 0;
int ocount = 1;
for(int i=0; i<no; i++){
if(a[i] == 0){
b[zcount]=0;
zcount++;
}else {
b[no-ocount] = 1;
ocount++;
}
}
System.out.println(Arrays.toString(b));

Hi all, sometimes you are asked to do this in one pass, without any other data structures. I think this is to avoid the solution of just summing the array and then creating a new array.

This is my answer in python. I am sure there are ways to make this better:

from array import array
a = array('i',[1,0,0,1,0,1,1,0,1,1,0,1])

ones = 0
sum = 0 ;

for i in range(0,len(a)):
   if a[i] == 1:
      ones += 1
   if a[i] == 0 & (ones > 0):
      a[i] = 1
      a[i-ones] = 0

int a[] = {0,0,0,0,0,0,1};		
		int currIndex=-1;

		for (int i = 0; i < a.length; i++) {
			if(a[i]==1){
				if(currIndex==-1)
					currIndex=i;
			}else{
				if(currIndex!=-1){
					a[currIndex]=0;
					a[i]=1;					
					currIndex=i;
				}
			}
		}

int[] array = new int[] { 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 };
int zerocount = 0;
int onescount = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] == 0)
{
if (i == 0)
{
zerocount += 1;
continue;
}
}

if (i > zerocount && array[i] == 0)
{
int temp = array[i - onescount];
array[i - onescount] = array[i];
array[i] = temp;
zerocount += 1;
}
else if (array[i] == 1)
{
onescount += 1;
}
}

public static void main(String[] args) {
		int arr[]= {1,1,1,0,1,0,0,1,0};
		int x=0;

		System.out.println("Hello JAved");
		for(int i=1; i<arr.length;)
		{
			if(arr[i]<arr[i-1])
			{
				x=arr[i];
				arr[i]= arr[i-1];
				arr[i-1]=x;
				if(arr[1]==1)  // preventing getting i value as negative
					i=1;
				else
				i--;
			}
			else
				i++;
		}
		for(int i=0;i<=arr.length-1;i++){
			System.out.print(" "+arr[i]+" ");
		}
	  }

public static void main(String[] args) {
int arr[]= {1,1,1,0,1,0,0,1,0};
int x=0;

System.out.println("Hello JAved");
for(int i=1; i<arr.length;)
{
if(arr[i]<arr[i-1])
{
x=arr[i];
arr[i]= arr[i-1];
arr[i-1]=x;
if(arr[1]==1) // preventing getting i value as negative
i=1;
else
i--;
}
else
i++;
}
for(int i=0;i<=arr.length-1;i++){
System.out.print(" "+arr[i]+" ");
}
}

The most efficient way to sort the array of 0s and 1s is to count the total number of 0s present in the array and to count the total number of 1s in the array and then traversing the array from 0 indexes to the count index insert 0 in the array and then next index to the end index insert 1 in the array and hence the array is sorted.

Implementation:

void sort-array(int arr[], int n){
	int count = 0;
	for(int i = 0; i < n; i++)
		if(arr[i] == 1)
			count++;
	for(int i = 0; i < temp; i++){
		arr[i] = 0;
	for(int i = temp; i < (n - temp); i++)
		arr[i] = 1;
}

quicksort; O(lgN)