lets assume numbers are in range 0 - 4 ,and array is aarr . then range
would be 0- 4^3 .. (0 - 64)..
now allocate an arraay .. int *x = calloc(n^3,sizeof(int)) // can use even
bits aalso .. but for simplicity of algo , using array
for(int i=0;i<4;i++)
{
x[arr[i]] = 1;
}
for(int i=0;i<64;i++)
{
if(arr[i]!=0)
{
x[i]=arr[i];
}
}
// it can be optimized by using bits ..
please correct me if i am wrong in understaanding the qquestion of any
issues in algo .
On Tue, Aug 16, 2011 at 3:18 AM, 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.
>
--
Thx,
--Gopi
--
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.
