Re: Arranging the keys problem

In article <1128024200.887357.322660@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
"mihir" <mirdesai81@xxxxxxxxx> 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)).

Since this sounds a lot like a homework problem, I will refrain from
answering this question with code. However, you will be well-served by
looking up the Radix Sort algorithm,

http://www.nist.gov/dads/HTML/radixsort.html

I hope this helps.

Cheers,
-M

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
.

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 ... Quicksort is an overkill. ... known as fat pivot partitioning. ...
    (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)