[algogeeks] Given an array of size n of 0 and 1 only sort it in linear time.

[Manu]

I know counting sort can do in linear time but we dont need to use and
extra space.
as we do in case of counting sort.


I came up with this sol. but i think it's not stable so if u can find a
stable algo plzzz....


i=0;j=n-1;

while(i<j) {
     if(a[i]==a[j]) {
        if(a[i]==0)
            i++;
        else
            j--;     //ie equal to 1
      continue; //ie go to  while (i<j)
     }
    if(a[i]<a[j])
       i++;       //ie a[i] has to be zero only
   else {         //ie a[i] =1 and a[j] = 0 therefore swap them
      swap(a[i],a[j]); 
      i++;
      j--;
   }
} //end of while


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---