Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #11962

Re: A simple sorting algorithm for numbers

Show all headers | View raw

user923005 kirjutas teisipäev, 20. november 2007 kl 07:33:45 UTC+2:
> On Nov 19, 5:46 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> > user923005 wrote:
> > > On Nov 19, 2:19 pm, "Alf P. Steinbach" <al...@start.no> wrote:
> > >> * user923005:
> > > [snip]
> > >> It seems you don't read the articles you're replying to.
> >
> > > Perhaps you would like to clarify. Actually I have read them. If you
> > > also believe that you cannot sort faster than O(n*log(n)) then you are
> > > wrong as well.
> >
> > The point is that the articles you have been replying to never claimed that
> > sorting cannot be done faster than O(n*log(n)). The claim was that sorting
> > needs to generate n * log(n) bits of information. This does not imply nor
> > has it been claimed to imply that sorting cannot be done faster than O( n *
> > log(n) ). It has only been claimed that this yields a lower bound on the
> > speed of _comparison based_ sorting algorithms. To quote yourself from
> > upthread:
> OK, comprehension problem on my part.
> > >> On Nov 16, 3:18 pm, Mark P <use...@fall2005REMOVE.fastmailCAPS.fm> wrote:
> > [snip]
> > >> Omega(n log n) is the worst case lower bound for comparison based sorts.
> > [snip]
> >
> > > That is true for comparison based sorts. Bucket sort is driven purely
> > > off the key and does not rely upon comparisons.
> >
> > As you can see, the post of Mark P that you replied to specifically claimed
> > the lower runtime bound for comparison based sorts. Everything that
> > followed can be described as violent agreement.
> A sort operation of N items requires log2(N!) bits of information to
> order the items, because we can always choose the adversary at every
> step.
> My claim was simply that there are sorts that do not require
> additional space and (because of their nature as distribution sorts)
> can sort in O(N) average time and O(NlogN) worst case time.
> So I suppose we all agree. Not sure how I came to the conclusion that
> the posts that followed mine were in disagreement.


503 Service Unavailable






He

ya12983 mail c o m
372 6861327

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: A simple sorting algorithm for numbers H E <jippii1291983@gmail.com> - 2021-01-23 01:22 -0800
  Re: A simple sorting algorithm for numbers Härra Ramob <ya12983@mail.com> - 2022-01-05 00:37 -0800

csiph-web