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