Array sorting

Discussion in 'C Programming' started by Ankur, May 15, 2009.

  1. Ankur

    Ankur Guest

    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??
     
    Ankur, May 15, 2009
    #1
    1. Advertising

  2. Ankur

    Guest

    On 15 May, 10:30, Ankur <> 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()?
     
    , May 15, 2009
    #2
    1. Advertising

  3. Ankur

    Willem Guest

    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, May 15, 2009
    #3
  4. Ankur

    Willem Guest

    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
     
    Willem, May 15, 2009
    #4
  5. Ankur

    Guest

    On May 15, 4:00 pm, 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.
    >
    > #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
     
    , May 15, 2009
    #5
  6. Ankur

    Gene Guest

    On May 15, 7:46 am, Richard Heathfield <> 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.
     
    Gene, May 15, 2009
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. markspace
    Replies:
    1
    Views:
    408
    markspace
    Jun 25, 2009
  2. Roedy Green
    Replies:
    1
    Views:
    453
    Roedy Green
    Jun 25, 2009
  3. Replies:
    2
    Views:
    1,489
    James Kanze
    Jul 6, 2010
  4. Dominic Son

    Sorting through an array of an array

    Dominic Son, Oct 13, 2006, in forum: Ruby
    Replies:
    5
    Views:
    90
  5. Andrew Poulos

    Sorting array against other array

    Andrew Poulos, Jan 17, 2007, in forum: Javascript
    Replies:
    4
    Views:
    108
    Andrew Poulos
    Jan 23, 2007
Loading...

Share This Page