wu :: forums
« wu :: forums - Sort »

Welcome, Guest. Please Login or Register.
Nov 28th, 2024, 12:49pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: Grimbal, william wu, SMQ, towr, Icarus, Eigenray, ThudnBlunder)
   Sort
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Sort  (Read 335 times)
mad
Junior Member
**





   


Posts: 118
Sort  
« on: Mar 7th, 2008, 10:45pm »
Quote Quote Modify Modify

Show how to sort n integers in the range 0 to n^2-1 in O(n) time.
I think convert the number into base2 and apply radix sort. Is this correct?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Sort  
« Reply #1 on: Mar 8th, 2008, 2:25am »
Quote Quote Modify Modify

What sort of computer do you have that doesn't already store numbers in binary?  Roll Eyes
 
I'm not sure whether the preferred answer is radix sort, but it works.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
m_aakash
Junior Member
**





   


Posts: 96
Re: Sort  
« Reply #2 on: Mar 8th, 2008, 1:39pm »
Quote Quote Modify Modify

if you use radix sort with radix 2 then it will take
O(n log(n^2-1)) time in worst case. this is no longer a linear solution.
« Last Edit: Mar 8th, 2008, 1:40pm by m_aakash » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board