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. Advertisements

  2. Ankur

    Guest Guest

    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()?
     
    Guest, May 15, 2009
    #2
    1. Advertisements

  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. Stop doing homework for these idiots.........
     
    jack.thomson.v3, May 15, 2009
    #5
  6. Ankur

    Gene Guest

    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. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.