Subj : Re: Arranging the keys problem
To   : comp.programming
From : cri
Date : Thu Sep 29 2005 10:06 pm

On Thu, 29 Sep 2005 20:20:26 +0000 (UTC), Willem <willem@stack.nl>
wrote:

>mihir wrote:
>) There are n keys of different 3 colors say white ,red and blue only.Now
>) we have to arrange keys such that red keys come before white ones and
>) white ones come before blue keys eg RWWBBB where the keys are placed in
>) any random order.Give me a linear time algorithm to solve this problem
>) ( O(n)).
>
>Quicksort.  You may need a slight tweak to make it linear time.

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.



Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.

.