Re: Arranging the keys problem

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. :-)

As an aside: this was probably a homework question from a class, that is
leading up to quicksort. The fact that he wanted to sort red, white and
blue is a dead giveaway that Dutch National Flag is the intended solution.


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: sorting an array of three kinds of stones
    ... >> your instructor has given you a trick question. ... this is the well known "Dutch Flag" problem, ... IIRC correctly "fat pivot" variant of quicksort uses the ... Dutch Flag algorithm. ...
    (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)
  • Re: Arranging the keys problem
    ... Quicksort is an overkill. ... known as fat pivot partitioning. ... That would be the slight tweak I was referring to. ... SaSW, Willem ...
    (comp.programming)