Re: Arranging the keys problem

Willem wrote:
) Richard wrote:
) ) Quicksort is an overkill. The canonical in place O(n) solution is the
) ) Dutch Flag Algorithm which, in the better quicksort implementations is
) ) known as fat pivot partitioning. The point is that the first
) ) partitioning pass suffices to solve the problem.
)
) That would be the slight tweak I was referring to. :-)

I just realised that you don't need any tweaks.
Quicksort is O(n) for a dataset containing only 3 possible symbols.
(Quicksort with a fat pivot, that is.)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: Arranging the keys problem
    ... Quicksort is an overkill. ... Dutch Flag Algorithm which, in the better quicksort implementations is ... known as fat pivot partitioning. ...
    (comp.programming)
  • Re: Arranging the keys problem
    ... >) Quicksort is an overkill. ... >) Dutch Flag Algorithm which, in the better quicksort implementations is ... >) known as fat pivot partitioning. ...
    (comp.programming)