@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>
> > .
> > 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
