Re: Arranging the keys problem


Lars Weber wrote:
> Hi Willem,
>
> You're wrong.
> Quicksort is not of linear runtime.
> In worstcase it's O(n²) and in the average it's O(n log n).
>
> Have a look here to get more information:
> http://en.wikipedia.org/wiki/Sorting_algorithms#List_of_sorting_algorithms

Actually, good implementations of quicksort (e.g., those that use
3-way partitioning / Dutch National Flag) are O(n) worst-case if
there are only a constant number of distinct elements.

Unfortunately, some textbook implementations are quadratic
when there are a constant number of distinct elements.

.

Relevant Pages

  • Re: Arranging the keys problem
    ... Lars wrote: ... Quicksort is not of linear runtime. ... In worstcase it's Oand in the average it's O. ... In the case of only three different elements, Quicksort *is* O. ...
    (comp.programming)
  • Re: Arranging the keys problem
    ... Quicksort is not of linear runtime. ... In worstcase it's Oand in the average it's O. ... Prev by Date: ...
    (comp.programming)