@Surender: Yes. Actually, I'm converting a[i]-1 into radix N. The most significant digit is (a[i]-1)/N, and the least significant digit is (a[i]-1)%N. You are right that the lsd should be before the msd. Thanks.
Dave On Aug 11, 8:44 am, surender sanke <[email protected]> wrote: > @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 <[email protected]> wrote: > > @Arun: Look up "Radix sort" and then read the comments in the code. > > > Dave > > > On Aug 3, 4:23 am, Arun Vishwanathan <[email protected]> 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 <[email protected]> wrote: > > > > @Dave, > > > > Can you please explain the algo? It's getting very difficult to > > understand > > > > the code .. > > > > > On 3 August 2011 01:14, Dave <[email protected]> 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 <[email protected]> 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 [email protected]. > > > >> To unsubscribe from this group, send email to > > > >> [email protected]. > > > >> 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 [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]. > > > > 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 [email protected]. > > To unsubscribe from this group, send email to > > [email protected]. > > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
