Subj : Re: Arranging the keys problem
To   : comp.programming
From : Willem
Date : Fri Sep 30 2005 12:12 pm

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

.