You are given an array of 0s 1s and 2s in random order. Sort the array so the o,1 and 2 are segregated.
This problem is similar to Dutch national Flag problem.
Method 1:
Use count sort logic.
void sort012(int *a, int n){ int i,j,k; int count[2]={0}; for(i=0;i< n;i++) { if(a[i]==0) count[a[i]]++; else if(a[i]==1) count[a[i]]++; else if(a[i]==2) count[a[i]]++; } for(i=0;i < count[0];i++) a[i]=0; for(j=i;j < i+count[1];j++) a[j]=1; for(k=j;k < j+count[2];k++) a[k]=2; for(i=0;i<n;i++) printf("%d",a[i]); }
Complexity: O(N)
Method 2:
1. Sort the array treating {0} as one group and {1, 2} as one group.
2. Now again sort the array of 1 & 2.
void swap(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } void sort012(int *a, int n) { i = 0; j = n-1; // first loop sorts the array with 0 at front and {1, 2} at end while (i <=j) { while (a[i] ==0) { i++; } while (a[j] == 1 || a[j] == 2) { j--; } swap(a,i,j); } // This loop sorts array of 1 & 2 i = j; j = n-1; while (i <=j) { while (a[i] ==1) { i++; } while (a[j] == 2) { j--; } swap(a,i,j); } }
Complexity: O(N)
Method 3:
Only traversing the array once.
void sort012(int[] a){ int low = -1; int mid = 0; int high = a.length; while(mid < high){ if(a[mid] == 0){ low++; swap(a, low, mid); mid++; }else if(a[mid] == 1){ mid++; }else if(a[mid] == 2){ high--; swap(a, mid, high); } } }
Complexity: O(N)
In this method, we traversed the array once.
Source : http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
https://oj.leetcode.com/problems/sort-colors/
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void sortColors(int A[], int n) {
int hi=n-1;
int lo=0;
int mid=0;
while(mid<=hi)
{switch(A[mid])
{
case 0:swap(&A[mid++],&A[lo++]);
break;
case 1:mid++;
break;
case 2:swap(&A[mid],&A[hi--]);
break;
}
}
}
https://oj.leetcode.com/problems/sort-colors/
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void sortColors(int A[], int n) {
int hi=n-1;
int lo=0;
int mid=0;
while(mid<=hi)
{switch(A[mid])
{
case 0:swap(&A[mid++],&A[lo++]);
break;
case 1:mid++;
break;
case 2:swap(&A[mid],&A[hi--]);
break;
}
}
}
Given Method 2 does not work. It goes into infinite loop.
In Method 2, after swapping a[i] & a[j], you have to i++ & j–.
Else it results in an infinite loop.
And in while condition, you have to add (i < j) condition.
Else it results in a wrong answer.
The final code here:
https://ideone.com/hlCx50
In Method 2, after swapping a[i] & a[j], you have to i++ & j–
Else it results in an infinite loop.
And in while condition, you have to add (i < j) condition.
Else it results in a wrong answer.
The final code here:
https://ideone.com/hlCx50