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