CareerCup

Just travel through the array, the first 1 found, store its position.
Continue till a zero is encountered, swap the positions.
Again start from the stored index of 1.
Continue till no. zero is found to the right to swap.

static public void sortZeroOne(int[] a) {
		if (a==null || a.length==1) return;
		int i=0;
		int j=a.length-1;
		while (i<j) {
			while (a[i]==0) i++;
			while (a[j]==1) j--;
			if (i<j) {
				a[i]=0; 
				a[j]=1; 
				i++; 
				j--;
			}
		}
		
	}

Pseudocode:

1) Find the point from start of array where zeros end
2) Find the point from end of array where ones end
3) Swap the two points
4) Increment zeros pointer by one and decrement ones pointer by one
5) Repeat steps 1-4 while (ones-zeros) > 1

public void sortArray (int[] input) {

	int zeros = 0, ones = input.length, current = 0;

	while ((ones-zeros) > 1){
	
		while ((zeros < ones) && (zeros < input.length)){
			if (array[zeros]==0){
				zeros++;
			} else {
				break;
			}
		}

		if (zeros < input.length){
			while ((ones > zeros) && (ones > 0)) {
				if (array[ones]==1){
					ones--;
				} else {
					break;
				}
			}
		}

		array[zeros]=1;
		array[ones]=1;
		zeros++;
		ones--;
	}
}

I think this can be done in order of n. Create a new array of same size and keep two pointers - one at start and one at the end. Now traverse the original array - every time you encounter a zero, keep it to the left of the new array and increment the left counter and if 1, put it on the right and decrement the left counter.

void sort(int arr[], int len) 
{ 
one=0; 
 while(one!=len)
 { 
if(arr[one]==1)
 {  temp=one; }
 one++; 
if(one!=len&&arr[one])
 { arr[temp]=0;
 arr[one]=1;
 }
 one=temp+1; 
} 
  }

void SortString(char data[])
{
	if (data != 0)
	{
		int len = strlen(data);
		if (len > 1)
		{
			int i = 0;
			int j = len - 1;
			while (i < j)
			{
				while(data[i] == '0')
					++i;

				while((i < j) && (data[j] == '1'))
					--j;

				if (i < j)
				{
					data[i++] = '0';
					data[j--] = '1';
				}
			}
		}
	}
}

void RunDriver()
{
	//input
	char data[1000];
	cin.getline(data, 1000);

	SortString(data);
	cout << endl << "the sorted string is: " << data << endl;
} //RunDriver

void sortIt(int *a, int n)
{
	int i,indx;

	for(i=0;i<n;i++)
	{
		if(a[i]==1)
		{
			indx=i;
			while(i<n)
			{
				if(a[i]!=0)
					i++;
				else
				{
					int tmp=a[i];
					a[i]=a[indx];
					a[indx]=tmp;
					i=indx;
					break;
				}
			}
		}
	}
}

/*
 Sorts the given binary array from the index 'from' to the index 'to'.
*/
void sortBinaryArray(int* array, int from, int to)
{
   int left = from;
   int right = to;

   while (left < right)
   {
       if(array[left] > array[right]) /* one before zero is not ok */
       {
          array[right--] = 1;
          array[left++] = 0;

          continue;
       }

       while(left < right && array[left] == 0) /* zero in the left is fine */
        left++;

       while(right > left && array[right] == 1) /* one in the right is fine */
        right--;
   }
}

Here is algo with o(n)
=============================================
public class SortZeroOne {

public static void main(String[] args) {

int[] number = {0,1,1,1,0,0,0,1,1,0};
sort(number);
for(int i=0;i<number.length;i++)
System.out.println(number[i]);

}

private static void sort(int[] numbers)
{
int[] ones = new int[numbers.length];
int oneStart=-1,oneEnd = -1;

for(int i=0;i<numbers.length;i++)
{
if(numbers[i] == 0){
if(oneStart != -1 && oneEnd != -1 && oneEnd < ones.length){
swap(numbers,i,oneStart++);
}
}
if(numbers[i] == 1){
if(oneStart == -1 && oneEnd == -1){
oneStart = oneEnd = 0;
ones[oneEnd] = i;
}
else
{
ones[++oneEnd] = i;
}

}

}

}

private static void swap(int[] numbers,int x,int y)
{
int tmp = numbers[x];
numbers[x] = numbers[y];
numbers[y] = tmp;
}

}

void sort(int[] arr)
{
	int Number_Of_Ones = 0;
	int Number_Of_Zeros = 0;
	for(int i = 0; i < arr.length; i++)
	{
		if(arr[i] == 0)
		{
			Number_Of_Zeros++;
		}
		if(arr[i] == 1)
		{
			Number_Of_Ones++;
		}
	}
	for(int i = 0; i < Number_Of_Zeros; i++)
	{
		arr[i] = 0;
	}
	for(int i = 0; i < Number_Of_Ones; i++)
	{
		arr[i] = 1;
	}
}

void sort(int[] arr)
{
	int Number_Of_Ones = 0;
	int Number_Of_Zeros = 0;
	for(int i = 0; i < arr.length; i++)
	{
		if(arr[i] == 0)
		{
			Number_Of_Zeros++;
		}
		if(arr[i] == 1)
		{
			Number_Of_Ones++;
		}
	}
	for(int i = 0; i < Number_Of_Zeros; i++)
	{
		arr[i] = 0;
	}
	for(int i = Number_Of_Zeros; i < Number_Of_Ones + Number_Of_Zeros; i++)
	{
		arr[i] = 1;
	}
}

#include<stdio.h>
#include<stdlib.h>
#define size(arr) sizeof(arr)/sizeof(arr[0])
int main(){
int arr[] = {1,0,0,0,1,0,1,1,1,0,1,1,0,1,0,0,1}, index=0,index_1=0;
int num_of_elems = size(arr);
int *result =malloc(num_of_elems*sizeof(int));
printf("Input : ");
for(;index <num_of_elems;index++){
printf("%d ", arr[index]);
if(1 == arr[index] )
result[num_of_elems-index-1] = arr[index];
}
printf("\nOutput : ");
for (index=0;index<num_of_elems;index++)
printf("%d ", result[index]);
printf("\n");
return 0;
}

Hi,
below is the code in which no extra array is required and can be done in o(n) (also simple to understand) .

private static int[] sort(int[] a) {
int i=0;
for(int k=1;k<a.length;k++){

if(a[i]==0){
i++;
continue;
}else{
if(a[k]==0){
int temp = a[i];
a[i]=a[k];
a[k]=temp;
i++;
}else{
continue;
}
}
}
return a;
}



-- Swetha Reddy Parava

Simple code which is doing this in O(n) with just O(1) space complexity.

char str[] = "11110000101010101011001";
	char *current = str;
	char *lastOne = NULL;

	for(int i = 0; i < strlen(str); i++)
	{
		if(str[i] == '1' && lastOne == NULL)
			lastOne = str + i;
		else if(str[i] == '0' && lastOne != NULL)
		{
			char ch = *lastOne;
			*lastOne = *current;
			*current = ch;

			lastOne++;
		}
		current++;
	}

public static int[] sortZeroOne(int[] a) 
        {
            int lastindex = a.Length-1;
            for (int i = 0; i <= lastindex;) 
            {
                if (a[i] > 0)
                {
                    int temp = a[i];
                    a[i] = a[lastindex];
                    a[lastindex] = temp;
                    lastindex--;
                    //dont increment i,we need to visit here again
                }
                else 
                {
                    i++;
                }
            }
            return a;
        }

#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int arr[5];
cout<<"enter elements";
for(int i=0;i<5;i++)
cin>>arr[i];
int n=4;
for(int i=0;i<=n;)
{
if(arr[i]==0)
i++;
else if(arr[i]==1)
{
int x=arr[n];
arr[n]=arr[i];
arr[i]=x;
n--;
}


}
for(int i=0;i<5;i++)
cout<<arr[i];
getch();
return 0;
}








#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int arr[5];
cout<<"enter elements";
for(int i=0;i<5;i++)
cin>>arr[i];
int n=4;
for(int i=0;i<=n;)
{
if(arr[i]==0)
i++;
else if(arr[i]==1)
{
int x=arr[n];
arr[n]=arr[i];
arr[i]=x;
n--;
}


}
for(int i=0;i<5;i++)
cout<<arr[i];
getch();
return 0;
}






#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int arr[5];
cout<<"enter elements";
for(int i=0;i<5;i++)
cin>>arr[i];
int n=4;
for(int i=0;i<=n;)
{
if(arr[i]==0)
i++;
else if(arr[i]==1)
{
int x=arr[n];
arr[n]=arr[i];
arr[i]=x;
n--;
}


}
for(int i=0;i<5;i++)
cout<<arr[i];
getch();
return 0;
}








#include<iostream>
#include<conio.h>
using namespace std;

int main()
{
int arr[5];
cout<<"enter elements";
for(int i=0;i<5;i++)
cin>>arr[i];
int n=4;
for(int i=0;i<=n;)
{
if(arr[i]==0)
i++;
else if(arr[i]==1)
{
int x=arr[n];
arr[n]=arr[i];
arr[i]=x;
n--;
}


}
for(int i=0;i<5;i++)
cout<<arr[i];
getch();
return 0;
}

static void sort(int[] input){
		int oneIndex=input.length-1;
		for(int i=0;i<input.length && i<oneIndex;i++){
			if(input[i]!=0){
				while(input[oneIndex]!=0){
					oneIndex--;	
				}
				input[i]=input[oneIndex];
				input[oneIndex]=1;
			}
		}
	}

An easier approach may be to search for 0's from right and store it in a location say pos0
and 1's from left and store it in a location say pos1
Then swap them.
Continue this till the pos1<pos0
complexity : O(n)

Here is the code :

#include<stdio.h>
main()
{
      int n,i,pos0,pos1;
      printf("Enter size of array : ");
      scanf("%d",&n);
      int a[n];
      for(i=0;i<n;i++)
      scanf("%d",&a[i]);

      pos0=n-1,pos1=0;
      while(pos1<pos0)
      {
                   if(a[pos1]==1 && a[pos0]==0)
                   a[pos1++]=0,a[pos0--]=1;
                   else if(a[pos1]==1)
                   pos0--;
                   else if(a[pos0]==0)
                   pos1++;
                   else
                   pos0--,pos1++;
      }
      printf("\n");
      
      for(i=0;i<n;i++)
      printf("%d ",a[i]);
}

A simple O(n) approach

#include<iostream>
using namespace std;
void sort01(int arr[],int size);
int main()
{
	int arr[] = {0,0,1,0,1,1,1,0,0,0};
	int size = sizeof(arr)/sizeof(arr[0]);
	for(int i=0;i<size;i++) cout<<arr[i]<< " ";
	sort01(arr,size);
	cout<<endl;
	for(int i=0;i<size;i++) cout<<arr[i]<< " ";
	cout<<endl;
	return 0;
}
void sort01(int arr[],int size)
{
	int h = size-1,l = 0;
	int temp;
	while(l<h)
	{
		while(arr[l] == 0 && l<h) l++;
		while(arr[h] == 1 && l<h ) h--;
		if(l<h){
				temp = arr[l];
				arr[l] = arr[h];
				arr[h] = temp;
				l++;
				h--;
				}
	}
}

sites.google.com/site/spaceofjameschen/home/sort-and-search/sort-an-array-which-only-has-0-s-and-1-s-do-not-use-count-sort-microsoft

Count the number of 0s and 1s in the first pass and save the values in say variables m and n. In the second pass, convert everything to 0 until m and remaining to 1. O(n) solution.

void sortanarray (int *array, int length) {
    int left = 0, right = length - 1;
    if(array == NULL || length == 0)
        return;
    while (left < right ) {
        if (array[left] == 1 && array[right] == 0) {
            array[left++] = 0;
            array[right--] = 1;
        } else if (array[left] == 1) {
            --right;
        } else if (array[right] == 1) {
            ++left;
        } else {
            ++left;
            --right;
        }
    }    
}

#include<stdio.h>
#include<conio.h>
void sort(int [],int);
main()
{
	int a[15]={1,1,1,0,1,1,0,1,0,0,1,1,0,0,0};
	int i;
	clrscr();
	sort(a,14);
	for(i=0;i<15;i++)
	{
		printf("  %d",a[i]);
	}
	getch();
}
void sort(int a[],int n)
{
	int j,i=-1,p,flag=0;
	for(p=0;p<=n;p++)
	{
	      if(flag==0 && a[p]==0)
		i++;
	      else if(flag==0 && a[p]==1)
	      {
		j=p;
		flag=1;
	      }
	      else if(flag==1 && a[p]==0)
	      {
		a[j]=0;
		a[p]=1;
		i=j;
		j=j+1;
	      }
	}
}

just use the partition function of quick sort..

It is just the first step of quick sort

Start from two ends left and right

left=0
right=size-1

let right and left approach each other until they cross

while( left < right )
{
	if( a[left] == 0 )
		left++;
	if( a[right] == 1 )
		right--;
	if( left < right && a[left] == 1 && a[right] == 0 )
		swap(a, left,right);
}

1) Make a linked list out of the array.
2) Traverse the linked list. for each 0 encountered, remove that node and make it the first node.

You will end up with a sorted list.

Time complexity O(n)
Space complexity O(n)

Use partition method (the one used in quick sort choosing 1 as a pivot), it will sort the array in O(N) in-place

Why not to take first and last. Compare them and swap if needed till you reach middle

int[] arr = new int[10] { 0, 0, 1, 0, 1, 0, 1, 0, 0, 1};
            int first = 0, last = arr.Length - 1,temp;
            
            while(first <= last)
            {
                if(arr[first] == 1)
                {
                    if (arr[last] == 0)
                    {
                        temp=arr[first];
                        arr[first] = arr[last];
                        arr[last] = temp;
                        first++;
                    }
                    last--;
                }
                else
                {
                    first++;
                }
            }