W Karas wrote:
> Manu wrote:
> > 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
>
> Could just do one quicksort-style pivot:
Oops.
i = 0;
j = n - 1;
while (i < j)
if (a[i] == 0)
i++;
else if (a[j] == 1)
j--;
else
{ a[i++] = 0; a[j--] = 1; }
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
