CareerCup

void sort(int array[]) {
int left, middle, right;
left=middle=0;
right = array.length - 1;
 while(middle < right) {
  if(array[middle] == 2) {
     swap(array[middle], array[right]);
     right = right - 1;
  }
  else if(array[middle] == 0) {
     swap(array[middle], array[left]);
     left++;
     middle++;
  }
  else {
     middle++;
  }

 }
}

I haven't tested the solution thoroughly, but this seems to be working.


# define N 12

int arr[N] ={2,1,2,2,1,0,0,1,1,2,0,1};
int zero=0,one=0;
int two=N-1;

void swap1()
{
if(arr[one+1]==1)
one++;
else
{
arr[zero]=arr[one+1];
arr[one+1]=1;
one++;
}
}

void swap2()
{
if(arr[two]==2)
two--;
else
{
arr[zero]=arr[two];
arr[two]=2;
two--;
}
}

int main()
{

for(;two-one>1;)
{
switch(arr[zero])
{
case 0: zero++;break;
case 1: swap1();break;
case 2: swap2();break;
}
}
return 0;
}

An unstable sort !

void sort( int A[] , int sz )
 {
     int lptr=0;
     int rptr=sz-1;
     
     while( lptr<rptr )
      {
            while( A[lptr]==0 )
             lptr++;
             
            while( A[rptr]!=0 )
             rptr-- ;
             
          if( A[lptr]!=0 && A[rptr]==0 )
           {           
            swap( A[lptr],A[rptr]);
            lptr++;
            rptr--;
            
            }
            
            }
            
           
     rptr=sz-1;
     
      
     while( lptr<rptr )
      {
            while( A[lptr]==1 )
             lptr++;
             
            while( A[rptr]==2 )
             rptr-- ;
             
          if( A[lptr]==2 && A[rptr]==1 )
           {           
            swap( A[lptr],A[rptr]);
            lptr++;
            rptr--;
            
            }
            
            }
            
         
         
         return ;
         
         }

it doesn't work...

search for dutch flag problem....this is similar to it :)

I guess this algorithm might work:

we can use four pointers p1,p2,p3,p4
p1 moves right from start, p2 moves left from middle
p3 moves right from middle, p4 moves left from end as shown below.

00000000 210112200102 1111111111111111 220101022001 22222222222222222
-------->P1 ...................... P2<-------- -------->P3 ......................... P4<--------------

correctness:
at every point we have,
0s to the left of p1,
1s between p2 and p3
2s to the right of p4

at the end
p1,p2 meet at intersection of 0s and 1s
p3,p4 meet at intersection of 1s and 2s

If an O(n) buffer is allowed i can see a single pass solution to the problem.
if not i can see a two pass solution, and now it would be intersting to see if this could be done in one pass with constant memory.

using 3 pointers and doing swap will do the job ..

if the last element in the array is 2 is it still working algo?

the 3 pointer and swap isn't stable

Please correct me if I am wrong. We maintain 2 pointer actually - a pointer corresponding to the beginning of region of 1 which in turn means the end of region of zero; similarly another pointer which marks the beginning of region of 2 and end of region of 1. After establishing the pointers from the first encounter of 0, 1 and 2, we keep scanning for each element. If the next element is 0, replace the current element with the pointer corresponding the first 2 and then move the first 1 to its place and put the current element 0 to the position left by first 1. Similarly we can deal with 1 and 2.

How about using Count sort ? We know the range is 1 - 3 . We can easily sort it in O(n) by simply counting the numbers by a single pass and then overwrite the array.
Please correct If wrong.

void swap(int* a, int* b){
*a ^= *b ^= *a ^= *b;
}
void printArr(int * arr, int num){
for(int i = 0; i < num; i++){
printf("%d, ", arr[i]);
}
printf("\n");
}
void sort012(){
int const N = 12;
int arr[N] = {2,1,2,2,1,0,0,1,1,2,0,1};
int * iter = arr;
int * p0 = arr;
int * p2 = arr + N - 1;


while(iter != p2)
{
switch(*iter){
case 0:
swap(p0, iter);
p0++;
break;
case 1:
iter++;
break;
case 2:
swap(p2, iter);
p2--;
break;
}
}
printArr(arr, N);
}

void swap(int* a, int* b){
	*a ^= *b ^= *a ^= *b;
}
void printArr(int * arr, int num){
	for(int i = 0; i < num; i++){
		printf("%d, ", arr[i]);
	}
	printf("\n");
}
void sort012(){
	int const N = 12;
	int arr[N] = {2,1,2,2,1,0,0,1,1,2,0,1};
	int * iter = arr;
	int * p0 = arr;
	int * p2 = arr + N - 1;


	while(iter != p2)
	{
		switch(*iter){
			case 0:
				swap(p0, iter);
				p0++;
				break;
			case 1:
				iter++;
				break;
			case 2:
				swap(p2, iter);
				p2--;
				break;
		}
	}
	printArr(arr, N);
}

/*
Using quicksort with two pointers (c) -Nikhil UIUC
------------------------
00000| 1111111|22222
------------------------
P1 P2
*/
int _tmain(int argc, _TCHAR* argv[])
{
int pointer1 =-1; //marks the boundary btw 0s and 1s
int pointer2 = -1; //marks the boundary btw 1s and 2s
int temp =0; //for exchange
int j =0; //for printing
// test case 1: int a[]={0,1,2,0,2,1,1,0}; int len = 8;
//test case 2: int a[] = {2,1,0,1,2,2,1,2,0}; int len = 9;
int a[]={2,0,1};int len=3;
for(int i =0; i < len; i++){
if(a[i] == 0){ //case when we encounter 0
pointer1=pointer1+1;
pointer2=pointer2+1;
//exchange element of pointer 2 with element of pointer 1
temp=a[pointer2];
a[pointer2]=a[pointer1];
a[pointer1]=temp;

//now exchange a[i] with pointer1
temp=a[i];
a[i] = a[pointer1];
a[pointer1] =temp;

}
if(a[i] == 1){ //when we encounter 1
//do regular quicksort
pointer2 = pointer2+1;
temp=a[i];
a[i]=a[pointer2];
a[pointer2]=temp;
}

}

while (j < len)
printf("%d \n", a[j++]);
return 0;
}

/*
Using quicksort with two pointers (c) -Nikhil UIUC
------------------------
00000| 1111111|22222
------------------------
     P1       P2
*/
int _tmain(int argc, _TCHAR* argv[])
{
	int pointer1 =-1; //marks the boundary btw 0s and 1s
	int pointer2 = -1; //marks the boundary btw 1s and 2s
	int temp =0; //for exchange
		int j =0; //for printing
	// test case 1: int a[]={0,1,2,0,2,1,1,0}; int len = 8;
	//test case 2: int a[] = {2,1,0,1,2,2,1,2,0}; int len = 9;
		int a[]={2,0,1};int len=3;
	for(int i =0; i < len; i++){
		if(a[i] == 0){ //case when we encounter 0
			pointer1=pointer1+1;
			pointer2=pointer2+1;
			//exchange element of pointer 2 with element of pointer 1
			temp=a[pointer2];
			a[pointer2]=a[pointer1];
			a[pointer1]=temp;

			//now exchange a[i] with pointer1
			temp=a[i];
			a[i] = a[pointer1];
			a[pointer1] =temp;

		}
		if(a[i] == 1){ //when we encounter 1
			//do regular quicksort
			pointer2 = pointer2+1;
			temp=a[i];
			a[i]=a[pointer2];
			a[pointer2]=temp;
		}

	}

    while (j < len)
	printf("%d \n", a[j++]);
	return 0;
}

When we start using quicksort in the worst case of the algorithm won't the complexity be nlogn which could violate the rule of the quest , as in one pass with complexity of n

Thought of this algorithm.


int leftIndex RightIndex =0
//Analysing this algorith, the number of cases for array[leftIndex],array[rightIndex] any of this algorithm are 9 cases {(0,0) (0,1) (0,2) (1,0) (1,1) (1,2) (2,0) (2,1) (2,2) }

while(leftIndex<RightIndex)
{
if(a[leftIndex==0]{)//eliminating cases (0,0)(0,1) (0,2)
leftIndex++
continue;}
if(a[RighIndex]==2){ //eliminating cases (2,2) (1,2)
rightIndex++
continue;}
if(a[leftIndex]>a[rightIndex])//cases are (1,0) (2,0) (2,1)
swap(a,leftIndex,rightIndex)
else if(a[leftIndex]==a[rightIndex]) // this is where the trivial part is to handle (1,1)
rightIndex =FindZero(a,rightIndex,leftIndex);


}

In findZero function do the following
initialize a variabel swapIndex = rightIndex
try to move the rightIndex until you either find a zero or you reach leftIndex
within the while loop swap if you find 2 inbetween with swapIndex and decrement swapIndex

void sort(int arr[], int n)
{
int i=0;
int begin = 0,end = n-1;
for(i=0;i<n;i++)
{
if ((arr[i] == 0) && (i> begin))
{
swap(arr[begin++],arr[i]);
}
if ((arr[i] == 2) && (i<end))
{
swap(arr[i],arr[end--]);

}
}
}

you also need to check whether you have swapped 2 and 0. you check whether arrary[i] is 0 first, it is not, so you will go to check whether arrary[i] is 2, it is currently, then you swap 2 with arrary[end], now arrary[end] is 0, arrary[i] is 0 after this swap, but you will go to arrary[i+1]now and will not swap the 0 with arrary[begin]

you also need to check whether you have swapped 2 and 0. you check whether arrary[i] is 0 first, it is not, so you will go to check whether arrary[i] is 2, it is currently, then you swap 2 with arrary[end], now arrary[end] is 0, arrary[i] is 0 after this swap, but you will go to arrary[i+1]now and will not swap the 0 with arrary[begin]

Hi all,
Thanks for the comment.
The problem is " we should not use for loop". This is because we should not increment i, if it is swapped. The modified algorithm is
void sort( int arr[], int n)
{
int i =0, begin=0, end = n-1;
while(i<=end)
{
if((arr[i] ==0) &&(i > begin)) swap(arr[i],arr[begin++]);
if(arr[i]==1)i++;
if((arr[i]==2) &&(i < end))swap(arr[i],arr[end--]);
}

A modification
void sort( int arr[], int n)
{
int i =0, begin=0, end = n-1;
while(i<=end)
{
if((arr[i] ==0) &&(i > begin)) {swap(arr[i],arr[begin++]);if(arr[i]==0)i++;}
if(arr[i]==1)i++;
if((arr[i]==2) &&(i < end))swap(arr[i],arr[end--]);
}

#include<iostream>

using namespace std;

void sort(int array[],int n) {
int left, middle, right;
left=middle=0;
right = n-1;
 while(middle <= right) {
  if(array[middle] == 2) {
     swap(array[middle], array[right]);
     right = right - 1;
  }
  else if(array[middle] == 0) {
     swap(array[middle], array[left]);
     left++;
     middle++;
  }
  else {
     middle++;
  }
}
}

int main()
{
int a[] = {2,0,2,1,0,1,2,2,0,2};
cout<<"Array Before: "<<a;
sort(a,10);
cout<<"Array After : "<<a;
return 0;

}

Use Quick sort algorithm and use 1 as the pivot element, in the first pass, the algorithm will arrange the array in desired order.

void sort012(int a[], int size)
{
	int l = 0;
	int r = size - 1;

	while (l < r)
	{
		while (a[l] == 0 && l < size)
			++l;

		while (a[r] == 2 && r >= 0)
			--r;

		if (a[l] == a[r]) // == 1
			break;

		std::swap(a[l], a[r]);
	}

	for (int i = l + 1; i < r; ++i)
		if (a[i] == 0)
		{
			std::swap(a[i], a[l++]);
		}

	for (int i = r - 1; i > l; --i)
		if (a[i] == 2)
		{
			std::swap(a[i], a[r--]);
		}

	std::swap(a[l], a[r]);
}

void sort012(int a[], int size)
{
int l = 0;
int r = size - 1;

while (l < r)
{
while (a[l] == 0 && l < size) ++l;
while (a[r] == 2 && r >= 0) --r;

if (a[l] == a[r]) // == 1
break;

std::swap(a[l], a[r]);
}

for (int i = l + 1; i < r; ++i)
if (a[i] == 0) std::swap(a[i], a[l++]);

for (int i = r - 1; i > l; --i)
if (a[i] == 2) std::swap(a[i], a[r--]);

std::swap(a[l], a[r]);
}

int get_parted(int a[],int p,int q,int x)
{
int i=p, j = q;
while(i<j)
{
if(a[i] ==x)
i++;
if(a[j] != x)
j--;
if((i<j)&&(a[i] != x) && (a[j] == x))
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
i++;
j--;
}
}
return (j+1);
}

void Three_sort(int a[],int n)
{
int p = get_parted(a,0,n-1,0);
get_parted(a,p,n-1,1);
}