@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.