 |  |  |  |  |  |  |  |
Question: Linear Time Sorting Problem
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
Thread Solved |
Hello, I have been asked to provide an algorithm for the following:
You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.
I have been unable to find any way to do it, due to the lack of a "hard" upper bound on the input range (Which varies with the size of input).
I'll be happy to hear ideas for anyone who can offer help. Thanks !
You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.
I have been unable to find any way to do it, due to the lack of a "hard" upper bound on the input range (Which varies with the size of input).
I'll be happy to hear ideas for anyone who can offer help. Thanks !
•
•
Join Date: May 2006
Posts: 1,580
Reputation: 
Solved Threads: 52
My first thought was a radix sort, but since that does depend on the value of the largest number, I'm don't think that it's strictly O(N) in this case.
I have tried Radix Sort, but since the number of digits is not fixed, it scales with size of input, due to that fact, in this case, the complexity would be O(nlogn), since log(base10)n is the amount of digits.
•
•
Join Date: May 2006
Posts: 1,580
Reputation:
Solved Threads: 52
Yeah, that's what I was thinking too. Even counting sort depends on the range of values, so it wouldn't fit either. I'm out of ideas, sorry 
Last edited by Infarction; Mar 31st, 2007 at 6:53 pm.
While I thank you for the reply - I already read the wikipedia entry for that, twice. I also spent a few hours on google, and reading "Introduction To Algorithms" (One of the authors is Cormen, another is Rivest, another is Stein, I don't recall the last one).
Any other ideas folks ?
Any other ideas folks ?
Last edited by Direwolf007; Apr 1st, 2007 at 9:57 am.
>> You are given an array of length N, which contains values in the range from 0 to (N^2) - 1. You are to sort it in O(N) time.
2 questions to understand the question:
1. Why does the range of value matter? (size/range of value would have no impact on the order of algorithm from what I know)
2. When you say "in O(N) time" do you mean it's an algorithm of order N or you really mean some number of mili/micro/seconds.. ?
2 questions to understand the question:
1. Why does the range of value matter? (size/range of value would have no impact on the order of algorithm from what I know)
2. When you say "in O(N) time" do you mean it's an algorithm of order N or you really mean some number of mili/micro/seconds.. ?
•
•
Join Date: May 2006
Posts: 1,580
Reputation:
Solved Threads: 52
1. It does affect algorithm runtime in several cases, especially when dealing with non-comparison based sorts (since it's proven that comparision based sorts cannot be guaranteed to run in better than O(n log n) time, they don't make the cut for this problem). Look at some of the sorts already mentioned in this thread.
2. Linear time with respect to the length of the input.
2. Linear time with respect to the length of the input.
•
•
Join Date: Jun 2006
Posts: 7,649
Reputation: 
Solved Threads: 474
Have you tried out SmoothSort ?
Its best case is O(n) and worst case is O(n log(n)) with the obvious downfall of difficult to implement.
Its best case is O(n) and worst case is O(n log(n)) with the obvious downfall of difficult to implement.
Last edited by ~s.o.s~; Apr 3rd, 2007 at 4:11 pm.
I don't accept change; I don't deserve to live.
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
Jo Tujhe Jagaaye, Nindein Teri Udaaye Khwaab Hai Sachcha Wahi.
Nindon Mein Jo Aaye Jise To Bhul Jaaye Khawab Woh Sachcha Nahi.
Khwaab Ko Raag De, Nind Ko Aag De
 |
Other Threads in the Computer Science Forum
- Previous Thread: Using flex and bison
- Next Thread: Instructor's manual
Views: 6547 | Replies: 29
| Thread Tools | Search this Thread |
Latest Computer Science Posts
- Today's Posts
- Unanswered Threads
Related Forum Features
Tag cloud for Computer Science
ai algorithm algorithms amazon assignment assignments automata battery bigbrother binary bizarre blogging bomb business cern clueless codebreaker computer computers computerscience computertrackingsoftware connect conversion dataintepretation development dfa dissertation dissertations dissertationthesis dissertationtopic ebook energy extensions floatingpoint foreclosure fuel gadgets geeks givemetehcodez government graphics hardware history homeowners homework homeworkhelp humor ibm idea ideas internet iphone itcontracts jobs kindle laser laws lazy linkbait lsmeans mainframes marketing mobileapplication msaccess nano netbeans networking news os p2p parser piratebay principles programming rasterizer research sam-being-cute sas science security sex spoonfeeding spying sql stephenfry student study supercomputer supercomputing syntactic technology textfield tree turing turingtest two'scompliment uk virus warehouse ww2
