stable algorithm with complexity O(n)

[Benjamin Kaplan]

2008/12/13 Aaron Brady <castironpi at gmail.com>

> On Dec 13, 1:17 pm, Duncan Booth <duncan.bo... at invalid.invalid> wrote:
> > "Diez B. Roggisch" <de... at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20081213/6e3e0423/attachment-0001.html>