Thursday, April 21, 2011

Sort an array having 0,1,2 without counting

1.Use 3 pointers low,mid & hi.
2.low will point to first element from left which is not 0
3. hi will point to first element from right which is not 2
4.low will not point to 2, except when low==mid
5.mid will move from 0 to hi and if it is 2, moves it to hi
and if it is 1 moves it to low.


public int[] group012(int[]arr)
{
int low=0,mid=0,hi=arr.length-1,temp=0;

while(mid<=hi)
{


switch(arr[mid])
{
case 0:
arr[mid++]=arr[low];
arr[low++]=0;
break;
case 1:
mid++;
break;
case 2:
arr[mid]=arr[hi];
arr[hi--]=2;
}

}

return arr;
}

No comments: