Re: quick sort and O(nlgn) worst case bound

Stephen Howe wrote:
It also happens to be the paper under discussion.
And as Jon Harrop has stated,
the paper does not apply to all quicksorts.

Yes does the paper apply to quicksorts where the pivot selection is O(1) ?
If the pivot selection is O(N) you can gurantee to get the median every time.

I think I am saying that all quicksorts will have at least 1 worst case if the pivot selection is O(1)

Um, did you mean what you just said? Surely *all* algorithms have at least 1 worst case?

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
.

Relevant Pages

  • Re: quick sort and O(nlgn) worst case bound
    ... And as Jon Harrop has stated, ... Yes does the paper apply to quicksorts where the pivot selection is O? ... If the pivot selection is Oyou can gurantee to get the median every time. ... Stephen Howe ...
    (comp.programming)
  • Re: quick sort and O(nlgn) worst case bound
    ... I think I am saying that all quicksorts will have at least 1 worst ... I think I am saying that for all quicksort algorithm where the pivot selection is O, there exists a family of distributions ... But it is only applied for the distributions that blow up. ...
    (comp.programming)
  • Re: quick sort and O(nlgn) worst case bound
    ... I think I am saying that all quicksorts will have at least 1 worst ... case that is Oif the pivot selection is O ... I have just been thinking about the existence of a lower bound. ...
    (comp.programming)