Wednesday, November 23, 2011

Sort array of 0s,1s and 2s in single scan


public static void main(String[] args){
int a[]={1,2,0,2,1,2,1,0,0,0,1,0,2,1};
int low=0,high=a.length-1;
int mid;
while(a[low]==0 && low<high)
 low++;
while(a[high]==2 && high>=0)
 high--;
mid=low;
while(mid<high)
{
if(a[mid]==0){
a[low]=0;
a[mid]=1;
low++;
mid--;
      }
else if(a[mid]==1)
mid++;
else{
a[mid]=1;
a[high]=2;
high--;
mid++;
}

}
for(int b : a)
System.out.print(b);


}

No comments:

Post a Comment