2008/12/13 Aaron Brady <castiro...@gmail.com> > On Dec 13, 1:17 pm, Duncan Booth <duncan.bo...@invalid.invalid> wrote: > > "Diez B. Roggisch" <de...@nospam.web.de> wrote: > > > > > > > > > David Hláčik schrieb: > > >> Hi guys, > > > > >> i am really sorry for making offtopic, hope you will not kill me, but > > >> this is for me life important problem which needs to be solved within > > >> next 12 hours.. > > > > >> I have to create stable algorithm for sorting n numbers from interval > > >> [1,n^2] with time complexity O(n) . > > > > >> Can someone please give me a hint. Would be very very thankful! > > > > > Unless I grossly miss out on something in computer science 101, the > > > lower bound for sorting is O(n * log_2 n). Which makes your task > > > impossible, unless there is something to be assumed about the > > > distribution of numbers in your sequence. > > > > > Who has given you that assignment - a professor? Or some friend who's > > > playing tricks on you? > > > > I think you must have fallen asleep during CS101. The lower bound for > > sorting where you make a two way branch at each step is O(n * log_2 n), > but > > if you can choose between k possible orderings in a single comparison you > > can get O(n * log_k n). > > > > To beat n * log_2 n just use a bucket sort: for numbers with a known > > maximum you can sort them digit by digit for O(n log_k n), and if you > don't > > restrict yourself to decimal then k can be as large as you want, so for > the > > problem in question I think you can set k=n and (log_n n)==1 so you get > > O(n) > > Minor detail: with k= n, you have log_n (n^2)= 2, so you get O(2n)= O > (n). Same answer. > > The generic sort theorems also assume you can compare arbitrarily > large numbers in constant time, which isn't true. That is, for any > given machine, there exist numbers that you can't compare on them in > constant time. But with a known upper bound k, you can just use a k- > bit machine. > > <rhetorical>So, what's the group policy on helping with homework? </ > rhetorical>
The policy is "don't do the homework for them". It's more for people who post "write a O(n) sort algorithm for integers in a range [0, n^2]" with a subject of "URGENT: RESPOND QUICKLY". The OP asked for advice on this problem, not for someone to give him the algorithm.
-- http://mail.python.org/mailman/listinfo/python-list
