@Ankur: The least significant digit of a[i], base n, is a[i]%n. The
middle digit is (a[i]/n)%n, and the most signficant digit is a[i]/
(n*n). So the code looks something like
int b[n], c[n], i, j;
for( i = 0 ; i < n ; ++i ) // sort by least significant digit
c[i] = 0;
for( i = 0 ; i < n ; ++i )
c[a[i]%n]++;
c[n-1] = n - c[n-1];
for( i = n-2 ; i >= 0 ; --i )
c[i] = c[i+1] - c[i];
for ( i = 0 ; i < 0 ; ++i )
b[c[a[i]%n]++] = a[i];
for( i = 0 ; i < n ; ++i ) // sort by middle digit
c[i] = 0;
for( i = 0 ; i < n ; ++i )
c[(b[i]/n)%n]++;
c[n-1] = n - c[n-1];
for( i = n-2 ; i >= 0 ; --i )
c[i] = c[i+1] - c[i];
for ( i = 0 ; i < 0 ; ++i )
a[c[(b[i]/n)%n]++] = b[i];
for( i = 0 ; i < n ; ++i ) // sort by most significant digit
c[i] = 0;
for( i = 0 ; i < n ; ++i )
c[a[i]/(n*n)]++;
c[n-1] = n - c[n-1];
for( i = n-2 ; i >= 0 ; --i )
c[i] = c[i+1] - c[i];
for ( i = 0 ; i < 0 ; ++i )
b[c[a[i]/(n*n)]++] = a[i];
// sorted result is in b[].
Dave
On Aug 15, 4:48 pm, Ankur Garg <[email protected]> wrote:
> @Dave
>
> Dude can u provide a sample code...What do u mean by radix n ..also radix
> sort requires some other sorting algo to sort digits
>
> Regards
> Ankur
>
>
>
> On Sun, Aug 14, 2011 at 1:33 PM, Dave <[email protected]> wrote:
> > @Ankur: Use a radix sort with radix n. It will take 3 passes to sort
> > the 3 base-n digits, each of O(n), so the overall order will be O(n).
>
> > On Aug 14, 10:08 am, Ankur Garg <[email protected]> wrote:
> > > This is one question from Coreman
>
> > > 3rd Edition -
>
> > > 8-3-4 -- Sort n integers in the range 0 to n^3 -1 in O(n) time
>
> > > Any ideas how to do this in O(n)
>
> > --
> > 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.
