This is similar to dutch flag problem. Here variable low manages the area of
0s, mid manages the area of 1s and high manages 2s. Start moving mid from
position 1, if it encounters a 0 swap with a[low] and increment both. If its
a 1, simply increment mid. If its a 2, swap with a[high] and decrement high.
void sort(int array[],int size)
{
int low=0;
int mid=0;
int high=size-1;
while(mid<=high)
{
switch(a[mid])
{
case 0: swap(&a[low++],&a[mid++]);
break;
case 1: mid++;
break;
case 2: swap(&a[mid],&a[high--]);
break;
}
}
}
time complexity: O(n)
space complexity: O(1)
On Wed, Jun 30, 2010 at 8:57 PM, Dave <dave_and_da...@juno.com> wrote:
> @Sathaiah. Why is this computationally harder? It takes a few lines
> more code to build a symbol table as the three symbols are discovered
> in the input data, but otherwise is pretty similar to Gene's code. So,
> during the second of Gene's loops, you have to search the symbol table
> for each array item. If it is not in the symbol table, you add it and
> set the count to 1. If the item is in the symbol table, you increase
> its counter by 1. In the while loop, j then is the index into the
> symbol table. You insert the item instead of its index into the array.
> Still O(n) in time and O(1) in space.
>
> Dave
>
> On Jun 29, 11:21 pm, Sathaiah Dontula <don.sat...@gmail.com> wrote:
> > @Gene, Your logic is specific to 0, 1 and 2.
> >
> > Let me change the problem, there are three different symbols in an array,
> > separate them in O(n) with O(1) space.
> >
> > Thanks,
> > Sathaiah
> >
> >
> >
> > On Wed, Jun 30, 2010 at 8:07 AM, Gene <gene.ress...@gmail.com> wrote:
> > > On Jun 29, 3:26 pm, sharad kumar <sharad20073...@gmail.com> wrote:
> > > > how to sort an array containing 0's 1's and 2's in O(n)time and
> sorting
> > > > technique must be inplace
> >
> > > #define M 3
> >
> > > void sort(int *a, int n)
> > > {
> > > int i, j, c[M];
> > > for (j = 0; j < M; j++) c[j] = 0;
> > > for (i = 0; i < n; i++) ++c[a[i]];
> > > for (i = j = 0; j < M; j++)
> > > while (c[j]--)
> > > a[i++] = j;
> > > }
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <algogeeks%2bunsubscr...@googlegroups.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
