Velocity Reviews > Array sorting

# Array sorting

Ankur
Guest
Posts: n/a

 05-15-2009
I have a array having 'r' 'g' 'b' as contents I want to arrange the
characters all at left all g at middle and all b at last of the array
in one pass. Any body can help me out??

nick_keighley_nospam@hotmail.com
Guest
Posts: n/a

 05-15-2009
On 15 May, 10:30, Ankur <(E-Mail Removed)> wrote:

> I have a array having 'r' 'g' *'b' as contents I want to arrange the
> characters all at left all g at middle and all b at last of the array
> in one pass. Any body *can help me out??

do you mean you actually have the characters 'r', 'g' and 'b' in your
array
or do you have some sort of encoding of colours?

Could you just sort the array with qsort()?

Willem
Guest
Posts: n/a

 05-15-2009
Richard Heathfield wrote:
) Ankur said:
)
)> I have a array having 'r' 'g' 'b' as contents I want to arrange
)> the characters all at left all g at middle and all b at last of
)> the array
)> in one pass. Any body can help me out??
)
) I don't think it's possible in one pass. But if you mean the above
) literally, it's quite easy to do it in /two/ passes, by simple
) counting.

Have you ever studied quicksort ?

PS: The colours are supposed to be red, *white* and blue.

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

Willem
Guest
Posts: n/a

 05-15-2009
Richard Heathfield wrote:
) Willem said:
)
)> Richard Heathfield wrote:
)> ) Ankur said:
)> )
)> )> I have a array having 'r' 'g' 'b' as contents I want to
)> )> arrange the characters all at left all g at middle and all
)> )> b at last of the array in one pass. [...]
)> )
)> ) I don't think it's possible in one pass. But if you mean the
)> ) above literally, it's quite easy to do it in /two/ passes, by
)> ) simple counting.
)>
)> Have you ever studied quicksort ?
)
) Yes, although perhaps not enough. So could you please explain why
) that's relevant, given that quicksort is typically O(n log n),
) whereas my solution is O(n)?

It's one of the steps of the quicksort algorithm. In fact, most
texts that teach sorting (and quicksort in particular) use the above
problem, in one form or another, to illustrate how quicksort works.

)> PS: The colours are supposed to be red, *white* and blue.
)
) That's not what the OP said. In fact, he didn't even mention colours
) (although I agree that 'r', 'g', 'b' do rather suggest a colour
) connection). You seem to be suggesting that he is not stating the
) problem correctly. Have I interpreted you correctly? Could you make
) yourself a little clearer?

The texts I mentioned above usually use 'r', 'w' and 'b' as the three
colours to be sorted. Also often used is 'l', 'm' and 'r'. I leave
it up to the reader to guess what those stand for.

Google for 'Dutch National Flag Algorithm'.

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

jack.thomson.v3@gmail.com
Guest
Posts: n/a

 05-15-2009
On May 15, 4:00*pm, Richard Heathfield <(E-Mail Removed)> wrote:
> Ankur said:
>
> > I have a array having 'r' 'g' *'b' as contents I want to arrange
> > the characters all at left all g at middle and all b at last of
> > the array
> > in one pass. Any body *can help me out??

>
> I don't think it's possible in one pass. But if you mean the above
> literally, it's quite easy to do it in /two/ passes, by simple
> counting.
>
> #include <stddef.h>
> #include <assert.h>
>
> void sortrgb(char *s, size_t len)
> {
> * unsigned long rcount = 0;
> * unsigned long gcount = 0;
> * unsigned long bcount = 0;
> * char *start = s;
> * while(*s != '\0')
> * {
> * * switch(*s)
> * * {
> * * * case 'r': ++rcount; break;
> * * * case 'g': ++gcount; break;
> * * * case 'b': ++bcount; break;
> * * * default: assert(0); /* assumptions are wrong */
> * * }
> * * ++s;
> * }
> * while(rcount--)
> * {
> * * *start++ = 'r';
> * }
> * while(gcount--)
> * {
> * * *start++ = 'g';
> * }
> * while(bcount--)
> * {
> * * *start++ = 'b';
> * }
> * assert(*start == '\0'); /* if I got the above right,
> * * * * * * * * * * * * * * *this assertion will not fire */
>
> * return;
>
> }
>
> --
> Richard Heathfield <http://www.cpax.org.uk>
> Email: -http://www. +rjh@
> Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
> "Usenet is a strange place" - dmr 29 July 1999

Stop doing homework for these idiots.........

--
Jack

Gene
Guest
Posts: n/a

 05-15-2009
On May 15, 7:46*am, Richard Heathfield <(E-Mail Removed)> wrote:
> Willem said:
>
> <snip>
>
> > Google for 'Dutch National Flag Algorithm'.

>
> Interesting. (And no, it seems I hadn't studied Quicksort "enough".)
>
> I'll take a longer look if I get time. (Given the existence of
> qsort, I probably take a more pragmatic view of sorting than
> perhaps I ought.)

There may be a language issue here and that he's really asking how to
transpose a Nx3 matrix of red-green-blue triples into a 3xN matrix of
color planes. If so, http://portal.acm.org/citation.cfm?id=362349.362368
is a good reference.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post boltar2003@boltar.world C++ 2 07-06-2010 09:40 AM Roedy Green Java 1 06-25-2009 08:25 PM markspace Java 1 06-25-2009 06:22 PM Andrew Poulos Javascript 4 01-23-2007 05:49 AM Dominic Son Ruby 5 10-13-2006 11:13 PM

Advertisments