CareerCup

Can be done in one pass (iterating through array only once)::

Following is code ::

int main() {
	int arr[] = {1,2,0,1,2,0,0,2,0,1,1,1,2,2,2,0,2,2,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,1,1};
	int len = sizeof(arr)/sizeof(arr[0]), elem, tmp, zero=0, two=len-1 , i = 0;
	while (i<len && two>=i){
		elem = arr[i];
	   if(elem==0) { arr[zero++]= elem; arr[i]=1; i++;}
	   if(elem==2) { tmp = arr[two]; arr[two--]= 2; arr[i]=tmp;}
	   if(elem==1) i++;
	}
	cout << endl;
	for(i=0;i<len;i++) cout << arr[i] << " " ;
	return 0;
}

This problem is a classic example of Quick3Way Sort:

sorting-algorithms(.com)/quick-sort-3-way

It could be done in O(n) time using count sort since the range of number is not that high.

I think in place sorting is not possible in O(n) time
int arr[]={2,1,2,0,2,1,0};
int tmp[]={1,1,1,1,1,1,1};//stores sorted array
int zp=0,tp=arr.length-1;

for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
tmp[zp++]=0;
if(arr[i]==2)
tmp[tp--]=2;
}

@ miki slight change in ur code

if(elem==0) { arr[zero++]= elem; if(i!=0)arr[i]=1; i++;}

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

void swap( int& x, int& y)
{
int temp = x;
x =y;
y=temp;
}

int main()
{
int arr[] = {0,1,2,0,1,2,0,0,2,0,1,1,1,2,2,2,0,2,2,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,1,1};
int i0 = 0;
int n = sizeof(arr)/sizeof(int);
int i2 = n-1;

for( int i=0; i<i2; )
{
switch (arr[i])
{
case 0:
swap(arr[i],arr[i0]);
i++;
i0++;
break;

case 2:
swap(arr[i],arr[i2]);
if(arr[i]!=2)
i++;
i2--;
break;

case 1:
i++;
break;

}
}

for (; i0<i2;)
arr[++i0] = 1;

cout << endl;
for(int i=0;i<n;i++ ) cout << arr[i] << " " ;

_getch();
return 0;
}

<pre lang="" line="1" title="CodeMonkey80201" class="run-this">#include <iostream>
#include <conio.h>
using namespace std;

void swap( int& x, int& y)
{
int temp = x;
x =y;
y=temp;
}

int main()
{
int arr[] = {0,1,2,0,1,2,0,0,2,0,1,1,1,2,2,2,0,2,2,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,1,1};
int i0 = 0;
int n = sizeof(arr)/sizeof(int);
int i2 = n-1;

for( int i=0; i<i2; )
{
switch (arr[i])
{
case 0:
swap(arr[i],arr[i0]);
i++;
i0++;
break;

case 2:
swap(arr[i],arr[i2]);
if(arr[i]!=2)
i++;
i2--;
break;

case 1:
i++;
break;

}
}

for (; i0<i2;)
arr[++i0] = 1;

cout << endl;
for(int i=0;i<n;i++ ) cout << arr[i] << " " ;

_getch();
return 0;
}</pre><pre title="CodeMonkey80201" input="yes">
</pre>

main()
{
int a[] = {0, 1, 2, 0, 1, 2, 0,1, 2, 2, 2, 0 , 2, 2, 0, 1, 0};
int tail0, head1, tail1, head2;
int n, i;

tail0 = head1 = tail1 = head2 = -1;

n = sizeof(a)/ sizeof(a[0]);
for (i = 0 ; i < n; i++){
printf("%d ", a[i]);
}
printf("\n");
tail0 = 0;
for (i = 0; i < n; i++) {
switch (a[i]) {
case 0:
if (tail0 == head1) {
if (tail1 == head2) {
a[i] = 2;
head2++;
}
a[tail1] = 1;
tail1++;
head1++;
}
a[tail0] = 0;
tail0++;
break;
case 1:
if (head1 == -1) {
if (head2 == -1)
head1 = tail1 = i;
else
head1 = tail1 = head2;
}
if (tail1 == head2) {
a[i] = 2;
head2++;
}
a[tail1] = 1;
tail1++;
break;
case 2:
if (head2 == -1)
head2 = i;
a[i] = 2;
break;
}
}

}

- Count the number of 0's, 1's, 2's - O(n).
- Write in the array 0, 1, 2 as per the above counters - O(n)

Thanks,
Laxmi

void 3WaySort(int data[] , int size )
  {
      int low=-1,high=size;
      int index=0;

      while( index < high )
       {
          if( data[index] ==0 )
           {
              swap(data[index],data[++low]);
              index++;
           }
           else if( data[index] ==2 )
            swap(data[index],data[--high]);
           else
             index++;
           
       }


  }

here is the code
logic is
1: traverse the array
2:if found 1 do nothing
2: if found 0 , swap it with 1 ( on left side)
3: if found 2 swap it with last. decrement last.

void swap(int a[],int first,int second)
{
int temp;
temp=a[first];
a[first]=a[second];
a[second]=temp;
}
void arrange(int a[],int size)
{
   int zero=0,one=0,two=size-1;
   while(one<=two)
   {
     switch(a[one])
      {
        case 0:
        swap(a,zero,one);
        zero++;
        one++;
        break;
        case 1:
        one++;
        break;
        case 2:
        swap(a,one,two);
        two--;
        break;

      }
   }
}