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. >> >> > > Solution given by Raj is more stable and inplace valid for any given input. > In terms of space it's better than counting sort. > http://codepad.org/z7xtx0nd > -- > 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.