@dave, ur converting array values into baseN and doing radix?
then every time there will be N*N = 100(baseN).
i think ur code doesn't works as ur checking against msd first(/) , then
lsd(%)
we need to exchange these operations, then it works fine.
surender
On Wed, Aug 3, 2011 at 3:55 PM, Dave <dave_and_da...@juno.com> wrote:
> @Arun: Look up "Radix sort" and then read the comments in the code.
>
> Dave
>
>
> On Aug 3, 4:23 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote:
> > yes dave it wud be better if u cud post an explanation of what u r doing
> in
> > each step..thanks
> >
> >
> >
> > On Wed, Aug 3, 2011 at 6:51 AM, payel roy <smithpa...@gmail.com> wrote:
> > > @Dave,
> > > Can you please explain the algo? It's getting very difficult to
> understand
> > > the code ..
> >
> > > On 3 August 2011 01:14, Dave <dave_and_da...@juno.com> wrote:
> >
> > >> @Pankaj: Assuming generously that by N^2 you mean N*N instead of N
> > >> exclusive-or 2, your very first statement is already O(N^2), as it
> > >> will take that long just to set the array to zero.
> >
> > >> Here is a radix sort to sort an array x[N] containing values from 1 to
> > >> N*N in O(N):
> >
> > >> int a[N], b[N], i;
> > >> // initialize and tally occurrences of first radix-N digit of x[i]-1:
> > >> for( i = 0 ; i < N ; ++i )
> > >> a[i] = 0;
> > >> for( i = 0 ; i < N ; ++i )
> > >> a[(x[i]-1)/N]++;
> > >> // compute starting point for each radix digit:
> > >> a[N-1] = N - a[N-1];
> > >> for( i = N-2 ; N >= 0 ; --i )
> > >> a[i] = a[i+1] - a[i];
> > >> // move numbers from array x to temp array b:
> > >> for( i = 0 ; i < N ; ++i )
> > >> b[a[(x[i]-1)/N]++] = x[i];
> >
> > >> // initialize and tally occurrences of second radix-N digit of x[i]-1:
> > >> for( i = 0 ; i < N ; ++i )
> > >> a[i] = 0;
> > >> for( i = 0 ; i < N ; ++i )
> > >> a[(x[i]-1)%N]++;
> > >> // compute starting point for each radix digit:
> > >> a[N-1] = N - a[N-1];
> > >> for( i = N-2 ; N >= 0 ; --i )
> > >> a[i] = a[i+1] - a[i];
> > >> // move numbers from temp array b back to array x:
> > >> for( i = 0 ; i < N ; ++i )
> > >> x[a[(x[i]-1)%N]++] = b[i];
> > >> // array is now sorted. Run time is O(N). Space is O(N).
> >
> > >> Dave
> >
> > >> On Aug 2, 11:04 am, pankaj kumar <pancsen...@gmail.com> wrote:
> > >> > int a[N^2]={0},i,j;
> > >> > for(i=0;i<N^2;i++)
> > >> > {
> > >> > cin>>j;
> > >> > a[j]++;
> >
> > >> > }
> >
> > >> > for(i=0;i<N^2;i++)
> > >> > {
> > >> > if(a[i]!=0)
> > >> > {
> > >> > while(a[i]--)
> > >> > {
> > >> > cout<<i<<"\t";
> >
> > >> > }
> > >> > }- 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 algogeeks@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.
> >
> > > --
> > > 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
> > > algogeeks+unsubscr...@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 algogeeks@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.
>
>
--
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
