Re: Arranging the keys problem

On Thu, 29 Sep 2005 20:20:26 +0000 (UTC), Willem <willem@xxxxxxxx>
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@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
I started out in life with nothing.
I still have most of it left.
.

Relevant Pages

  • Re: Thin Paint
    ... Now can i ask you something mate? ... have found a good looker but i'm told i need a red and brown key for ... red keys and doesn't know what i'm on about. ... Standard issue is 2 red keys. ...
    (uk.rec.cars.misc)
  • Re: Arranging the keys problem
    ... > 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 ... > any random order.Give me a linear time algorithm to solve this problem ... Since this sounds a lot like a homework problem, ...
    (comp.programming)
  • Re: Arranging the keys problem
    ... 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 ... You may need a slight tweak to make it linear time. ...
    (comp.programming)
  • Re: Arranging the keys problem
    ... >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 ... >any random order.Give me a linear time algorithm to solve this problem ... IOW provide a stable quicksort. ...
    (comp.programming)