Subj : Re: Arranging the keys problem
To   : comp.programming
From : cri
Date : Sun Oct 02 2005 01:58 pm

On 29 Sep 2005 13:03:20 -0700, "mihir" <mirdesai81@gmail.com> 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)).

Added requirement: The rearrangement must be stable, i.e, all of the
keys of a given color remain in the same order as they were
originally.  As before use O(n) time and O(1) additional space.
IOW provide a stable quicksort.

 

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.

.