http://geeksforgeeks.org/?p=8133 has the complete solution
On Thu, Jul 1, 2010 at 5:33 AM, jalaj jaiswal <jalaj.jaiswa...@gmail.com>wrote:
> in this case counting sort is inplace as how long the input array be ..the
> auxilary array will be of soze 3 only.. and counting sort is stable too
>
>
> On Thu, Jul 1, 2010 at 7:43 AM, Gene <gene.ress...@gmail.com> wrote:
>
>> On Jun 30, 12:21 am, Sathaiah Dontula <don.sat...@gmail.com> wroe:
>> > @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
>>
>> Well, your problem was specific to 0, 1, and 2.
>>
>> Arbitrary symbols are no different. You just create a lookup table
>> that maps the symbols to 0,1,2 and look them up as needed. In the
>> code below I made the lookup table s myself, but you could easily do
>> it with a O(n) preprocessing pass.
>>
>> #include <stdio.h>
>>
>> #define M 3
>>
>> int idx(int *s, int ai)
>> {
>> int i = 0;
>> for (i = 0; i < M; i++)
>> if (s[i] == ai) return i;
>> return -1;
>> }
>>
>> void sort(int *s, 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[idx(s, a[i])];
>> for (i = j = 0; j < M; j++)
>> while (c[j]--)
>> a[i++] = s[j];
>> }
>>
>> int main(void)
>> {
>> int i, s[] = {'a','b','c'}, a[] =
>> { 'c','c','a','b','a','b','c','a','c'};
>> sort(s, a, sizeof a / sizeof a[0]);
>> for (i = 0; i < sizeof a / sizeof a[0]; i++)
>> printf("%c ", a[i]);
>> printf("\n");
>> return 0;
>> }
>>
>> --
>> 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.
>>
>>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> 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.
