CareerCup

You don't have to create another array. Just have two pointers (begin and end). Begin pointer points at the beginning of the array while the end pointer points at the end of the array.

while (true)
{
while (*begin == 0)
++begin

while (*end == 1)
--end;

if (begin < end)
swap(begin end)
else
break
}

Soln having two pointers looks nice, however the term "SWAP" used more frequently. Please note that swapping is a costly affair and shall be used when both the values are changing time to time. Knowing the fact that values can be 0 and 1. We can say chage the value 0 to 1 or 1 to 0. Please comment if i am wrong.

If we are allowed to store the result in another array, then we could start assigning 0 from the begining of the array and 1s from the last. This could be done in linear time

Take two pointers. one at the start of the array and the other at the end of the array.The front pointer will attend to zero presence and the back to 1 presence.We compare with the value pointed by the front and the back .If front pointer value is 0 then increment it .If back pointer value is 1 decrement it.If front value is 1 and back value is 0 exchange.Do this unless boththe pointers meet.

How abt using a simple piegion hole sort?
Keep counting the # of 1s and 0s as u parse the array once. Reconstruct the array from the count. This is a linear sort.(O(n))

#include<stdio.h>
int main(){
int a[10]={0,1,1,1,0,1,0,0,0,1};

int i,j,temp;

i=0;
j=9;
while(i<j){
if(a[i]==0)
i++;
else{
while(a[j]==1 && j>i)
j--;

if(j>i){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}





}

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

It takes only O(n) time.........

to do it in one pass i think the no of elements
shall be known.
suppose no of elements are n.
then following works well.
#define MAX n
#include<stdio.h>
int main(){
int a[MAX]={0,1,1,1,0,1,0,0,0,1.......};

int i,j,temp;

i=0;
j=9;
while(i<j){
if(a[i]==0)
i++;
else{
while(a[j]==1 && j>i)
j--;

if(j>i){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
j--;
}
}

}

printf("\n\nSorted Data: ");
for(i=0;i<MAX;i++)
printf(" %d",a[i]);
}

You dont need to know the size of the array. Have 2 pointers, as you encounter a 0, increment both pointers and if you encounter a 1, increment only one of the pointers till you meet the next 0, when you will replace the 1 pointed by the first pointer to the 0 pointed by this new pointer. At the end of the iteration, you will have 0,s and 1's and the first pointer will be pointing to the starting of the 1's

really nice!!!!!!!!

start from the beginning.
if u encounter a 1 for the first time, store the position in a variable.

if u encounter ones progress

if u encounter zero, swap it with the position of 1 that u have stored in the variable and increment the variables value with 1

at the end of the iteration, the array would be sorted.

well. let's stick with the idea of having two cursors: Left, and Right.
Since there can be only 0s and 1s, we can possibly think of 4 different comparisons for Left and Right pointers.
1. Left:0, Right:0. Increase Left cursor.
2. Left:0, Right:1. Increase Left, decrease Right cursor.
3. Left:1, Right:0. Swap them. Increase Left, decrease Right cursor.
4. Left:1, Right:1. Decrease Right cursor.

Do this until Left < Right.

Let's translate this to code.

public int[] sortBinaryArr(int[] inArr) {
int leftCur=0;
int rightCur= inArr.length -1;

while (leftCur < rightCur) {
if (inArr[leftCur] == 0 && inArr[rightCur] == 0) {
leftCur++;
} else if (inArr[leftCur]==0 && inArr[rightCur] == 1) {
leftCur++;
rightCur--;
} else if (inArr[leftCur]==1 && inArr[rightCur] == 0) {
int temp = inArr[left];
inArr[leftCur] = inArr[rightCur];
inArr[rightCur] = temp;
leftCur++;
rightCur--;
} else if (inArr[leftCur]==1 && inArr[rightCur] == 1) {
rightCur--;
} else {
System.out.println("invalid value");
}
return inArr;
}

}

I think this might work.

#include<stdio.h>
int main(){
int a[10]={0,1,1,1,0,0,1,1,1,0};

int i,j,temp;

i=0;
j=0;
while(j<10){
if(a[i]==0){
i++;
j++;
}
else if (a[i]==1 && a[j]==1)
j++;

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


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

Count number of 0s (Rest are all 1s)
for i = 1 to count(0)
put 0
for i=count(0)+1 to n
put 1

O(n) time, 1 integer space.

ok my logic is simple, to do in in a single pass always store the position of the left most 1 and keep swapping zeros seen after seeing the leftmost 1 with the left most 1, after swap update the left most 1 to see if its the left most 1

private int[] sort(int[] is) {
int leftmost = -1;
for(int i = 0;i < is.length ; i++){
	if(is[i] == 1){
	 if(leftmost < 0)
           leftmost = i;
	 else
	   leftmost = Math.min(leftmost, i);
	}
	if(is[i] == 0 && leftmost >= 0){
          int l = leftmost+1;
	  is[leftmost] = 0;
	  is[i] = 1;
	  leftmost = i;
	  if(is[l] == 1)
	     leftmost = l;
	  }
	}
		return is;
  }

I think Srinivasan solution is the most smart one .

use two pointers where p1 will find the number of ones and p2 will point to the location from which ones should be filled in one traversal ....
let p1 ,p2 be two pointers
increment only p1 when u see an 1
increment p1 p2 when u see 0

#include<iostream>
using namespace stdin;
void sort(int *arr , int length)
{
int p1=0,p2=0;

while(p1<length)
{
if(arr[p1]==1)
{ arr[p1]=0;p1++;}
else
{ p1++;p2++; }
}

while(p2<len)
{ arr[p2++]=1;}

}

void SortZeroOnes( int *pArr, int len )
{
int i = 0;
int oneIdx = -1;
int toSwap = 0;

while( i < len )
{
if( pArr[i] == 1 )
{
if( toSwap == 0 )
{
oneIdx = i;
toSwap = 1;
}
}
else // pArr[i] == 0
{
if( toSwap == 1 )
{
int temp = pArr[ i ];
pArr[i] = pArr[oneIdx];
pArr[oneIdx] = temp;
oneIdx++;
}
}
i++;
}

for(int i = 0; i < len; i++ )
{
cout<<pArr[i]<<" ";
}
}

#include <iostream>

using namespace std;
inline void swap(int &a, int &b){int tmp; tmp = a; a=b; b=tmp;}

void sortBin(int *binAry, int size)
{
int i=0, j=size-1;
for(i=0, j=size-1; i!=j; ){
if(binAry[i] != binAry[j] && binAry[i] == 1 && binAry[j] == 0)
swap(binAry[i], binAry[j]), ++i, --j;
else if(binAry[i] != binAry[j] && binAry[i] == 0 && binAry[j] == 1)
++i, --j;
else if(binAry[i] == binAry[j] == 0)
++i;
else if(binAry[i] == binAry[j] == 1)
--j;
}
}

Here is the code..

#include<stdio.h>
#include<stdlib.h>
void main()
{
	int a[100],n,start,end,i;	
	printf("Enter the no. of elements in the array \n");
	scanf("%d", &n);
	printf("Enter the elements of the array \n");
	for(i=0;i<n;i++)
	{
		scanf("%d", &a[i]);
		if(a[i] != 0 || a[i] != 1)
			printf("Wrong Input \n");
		exit(0);
	}
	start = 0;
	end = n-1;
	while(start < end)
	{
		if(a[start] == 1 && a[end] == 0)
		{
			a[start++] = 0;
			a[end--] = 1;
		}
		else if(a[start] == 1 && a[end] == 1)
				end--;
		else 
			start++;
	}//End of while
	printf("The sorted array is \n");
	for(i=0;i<n;i++)
		printf("%d ", a[i]);
}

O(n) using one pointer to iterate and one extra variable to point to separate the sorted and unsorted portions of the array. Also the size is not needed, and here I have -1 as the terminator.

void sortBinaryArray(int *arrayToSort)
{
	int *array = arrayToSort;
	int *firstOne = NULL;

	while (*array != -1)
	{
		if (*array == 1)
		{
			firstOne = array;
			break;
		}
		array++;
	}

	while (*array != -1)
	{
		if (*array == 0)
		{
			int tmp = *firstOne;
			*firstOne = *array;
			*array = tmp;
			firstOne++;
		}
		
		array++;
	}
}

int ptr1=0,ptr2=N-1;

while(ptr1<ptr2)
{
if(arr[ptr1]==1 && arr[ptr2]==0)
{
swap(arr[ptr1],arr[ptr2]);
ptr1++;
ptr2--;
}

else if(arr[ptr1]==0)
ptr1++;

else if(arr[ptr2]==0)
ptr2--;

}

Instead of all the pointer mumbo jumbo count the number of 0s (say n) in the array and then make the first n elements of the array 0 and make the rest 1.

public class sortBinaryArray{

int test[] = {0,1,0,0,1,1,0,1,0,0,0,1,1,1,0,1,0};

public void sort(){

int lo = 0;
int hi = test.length -1;
int temp;

while(lo<hi)
{
while(test[lo] ==0 && lo< hi){ lo++;}
while(test[hi] == 1 && hi> lo){ hi--;}

temp = test[lo];
test[lo] = test[hi];
test[hi] = temp;

}
for(int i =0 ; i< test.length; i++)
System.out.println(test[i]);

}

public static void main(String args[])
{
sortBinaryArray sb = new sortBinaryArray();
sb.sort();

}


}