# Array sorting

A

#### Ankur

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??

G

#### 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??

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()?

W

#### Willem

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

W

#### Willem

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

J

#### jack.thomson.v3

Ankur said:

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. [email protected]
"Usenet is a strange place" - dmr 29 July 1999

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

G

#### Gene

Willem said:

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.