HELP ME on Sorting Characters.

[Bailey.W87]

my professor give me this assignment. Sort the R's B's and W's in an
array. for example, the user enter:

R B W W B B R W W R R W R B W

i need to swap the characters in the array and arrange it into

R R R R R W W W W W W B B B B

--------------------------------------------------------------------
i am thinking if i can set the R's = 1 W's=2 B's =3 then sort it out as
number from small to largest.

this is what i have so far.

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char *flag ) {
char 'R'=1;
char 'W'=2;
char 'B'=3;
printf("Please Enter Letters R's W's B's Only\n");
gets(flag);

}
int getlargest(double array[ ], int size) {
int index=0;
double big = array [ index];
int i;
for( i=1; i < size; i++) {
if (array> big;
index=1;
}
}
return index;
}


void sortFlag( char array[ ], int size) {
int end;
int large;
int lastplace= size -1 ;
double temp;
for (end=lastplace; end> 0; end --) {
large=getlargest(array, end+1);

temp=array[large];
array[index]=array[end];
array[end]=temp;
}
}

int main () {
char flag[MAX];
getchars(flag);
printf(flag);
return 0;
}

 

[fb]

my professor give me this assignment. Sort the R's B's and W's in an
array. for example, the user enter:

R B W W B B R W W R R W R B W

i need to swap the characters in the array and arrange it into

R R R R R W W W W W W B B B B

--------------------------------------------------------------------
i am thinking if i can set the R's = 1 W's=2 B's =3 then sort it out as
number from small to largest.

this is what i have so far.

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char *flag ) {
char 'R'=1;
char 'W'=2;
char 'B'=3;
printf("Please Enter Letters R's W's B's Only\n");
gets(flag);

1st, Never EVER EVER use gets. You can use fgets, or scanf (if you are
careful)

Also, proper indenting would help.

<SNIP>

As for th

 

[Bailey.W87]

ooo thanks. because when i try to complie it. it keep giving me errors
not until i put *in front of flag. but i have one question.

Does it work if i assign the R's = 1 , W's =2 , B's = 3 then i sort it
out from small to biggest?

 

[Chad]

my professor give me this assignment. Sort the R's B's and W's in an
array. for example, the user enter:

R B W W B B R W W R R W R B W

i need to swap the characters in the array and arrange it into

R R R R R W W W W W W B B B B

--------------------------------------------------------------------
i am thinking if i can set the R's = 1 W's=2 B's =3 then sort it out as
number from small to largest.

this is what i have so far.

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char *flag ) {
char 'R'=1;
char 'W'=2;
char 'B'=3;
printf("Please Enter Letters R's W's B's Only\n");
gets(flag);

}
int getlargest(double array[ ], int size) {
int index=0;
double big = array [ index];
int i;
for( i=1; i < size; i++) {
if (array> big;
index=1;
}
}
return index;
}


void sortFlag( char array[ ], int size) {
int end;
int large;
int lastplace= size -1 ;
double temp;
for (end=lastplace; end> 0; end --) {
large=getlargest(array, end+1);

temp=array[large];
array[index]=array[end];
array[end]=temp;
}
}

int main () {
char flag[MAX];
getchars(flag);
printf(flag);
return 0;
}

Just glancing over the code, I noticed that the array flag[MAX] is
local. Let's see if I can word this correctly. When this gets passed to
getchars() and getchars() stores the
information, it is in a local variable. In other words, when the
function returns, the information will no longer be in the array.

Maybe I'm wrong.

Chad

 

[Bailey.W87]

ok this is what i have so far. but when i try to complie it . it give
me a syntax error before 'R'

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char flag) {
char 'R'= 1;
char 'W'= 2;
char 'B'= 3;
printf("Please Enter ONLY letters R's W's and B's. \n ");
scanf("%s",&flag);
}

void printArray( double array[ ], int size) {
int i;

for( i=0; i<size; i++) {
printf("%lf ", array);
} // end for

printf("\n\n");
} // end printArray
int getLargestIndex( double array[ ], int size) {
int indexOfBig = 0;
double big = array[indexOfBig];
int i;

for(i=1; i < size; i++ ) {
if( array > big ) {
big = array;
indexOfBig = i;
} // end if
} // end for
return indexOfBig;
} // end getLargestIndex

void selectionSort( double array[ ], int size) {
int end;
int largeIndex; // holds index of largest value in set
int lastPlace = size -1; // holds index of last place in set
double temp;

for( end=lastPlace; end > 0 ; end-- ) {
largeIndex = getLargestIndex( array, end+1);
printf("largePlace: %d value: %lf\n", largeIndex, array[largeIndex]);
temp = array[largeIndex];
array[largeIndex] = array[end];
array[end] = temp;
printArray( array, size);
} // end for
} // end selectionSort


int main( ) {
double data[MAX];
selectionSort( data, MAX);
printArray( data, MAX);

return 0;

 

[Richard Bos]

my professor give me this assignment. Sort the R's B's and W's in an
array. for example, the user enter:

R B W W B B R W W R R W R B W

i need to swap the characters in the array and arrange it into

R R R R R W W W W W W B B B B

If you want the cheap hack solution that probably doesn't satisfy your
professor very much but is very good for large arrays of a limited,
fixed number of entries, do a websearch on "Counting Sort".

For a C solution, try qsort().

Richard

 

[Suman]

ok this is what i have so far. but when i try to complie it . it give
me a syntax error before 'R'

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char flag) {
char 'R'= 1;
char 'W'= 2;
char 'B'= 3;

'R', 'W' and 'B' are character literals. You cannot have them as
variable names. That's
where you get the compile-error.
Try something like:
char red = 1;
char white = 2;
char blue = 3;

printf("Please Enter ONLY letters R's W's and B's. \n ");
scanf("%s",&flag);

Again, 'c' and not 's' is the conversion specifier for characters.
Also, reading in a
single character like that may lead to confusion.

}

void printArray( double array[ ], int size) {
int i;

for( i=0; i<size; i++) {
printf("%lf ", array);

'array' is an array of doubles, and printf() takes f as the conversion
specifier
for doubles. And thus -- UB!

} // end for

This style of commenting was introduced pretty late in the C standard,
so beware!

printf("\n\n");
} // end printArray
int getLargestIndex( double array[ ], int size) {
int indexOfBig = 0;
double big = array[indexOfBig];
int i;

for(i=1; i < size; i++ ) {
if( array > big ) {
big = array;
indexOfBig = i;
} // end if
} // end for
return indexOfBig;
} // end getLargestIndex

void selectionSort( double array[ ], int size) {
int end;
int largeIndex; // holds index of largest value in set
int lastPlace = size -1; // holds index of last place in set
double temp;

for( end=lastPlace; end > 0 ; end-- ) {
largeIndex = getLargestIndex( array, end+1);
printf("largePlace: %d value: %lf\n", largeIndex, array[largeIndex]);

'array' is an array of doubles, and printf() takes f as the conversion
specifier
for doubles. And thus -- UB!

temp = array[largeIndex];
array[largeIndex] = array[end];
array[end] = temp;
printArray( array, size);
} // end for
} // end selectionSort


int main( ) {
double data[MAX];
selectionSort( data, MAX);
printArray( data, MAX);

return 0;

'}' at the end of main() (i.e. after return 0 would have been the
right way to sign off


<OT>
As an aside, you may also want to look up the Dutch National Flag
Algorithm,
but then that's a different story altogether...
</OT>

HTH

 

[Bailey.W87]

thats what i am doing. sorting the dutch national flag. anyway soultion?

 

[Suman]

thats what i am doing. sorting the dutch national flag. anyway soultion?

Quote, to avoid confusion. I admit not having read your code wholly,
but if you are
already using it, it's wonderful.

And I don't understand your question.

 

[Bailey.W87]

my question is is there any simple solution to this problem. i been
doing this the whole day. cant get it work

 

[slebetman]

my professor give me this assignment. Sort the R's B's and W's in an
array. for example, the user enter:

R B W W B B R W W R R W R B W

i need to swap the characters in the array and arrange it into

R R R R R W W W W W W B B B B

--------------------------------------------------------------------
i am thinking if i can set the R's = 1 W's=2 B's =3 then sort it out as
number from small to largest.

this is what i have so far.

#include <stdio.h>
#include <string.h>
#define MAX 81

void getchars(char *flag ) {
char 'R'=1;
char 'W'=2;
char 'B'=3;
printf("Please Enter Letters R's W's B's Only\n");
gets(flag);

}
int getlargest(double array[ ], int size) {
int index=0;
double big = array [ index];
int i;
for( i=1; i < size; i++) {
if (array> big;
index=1;
}
}
return index;
}


void sortFlag( char array[ ], int size) {
int end;
int large;
int lastplace= size -1 ;
double temp;
for (end=lastplace; end> 0; end --) {
large=getlargest(array, end+1);

temp=array[large];
array[index]=array[end];
array[end]=temp;
}
}

int main () {
char flag[MAX];
getchars(flag);
printf(flag);
return 0;
}

Does anyone here understand the part:

char 'R'=1;
char 'W'=2;
char 'B'=3;

This has no meaning in C, at least not the meaning the author intended.
First, the syntax error is you cannot quote a variable name. In this
case the C compiler sees an attempt to declare the variables R, W and B
and throws out an error when it sees the variable names quoted.

You don't seem to understand what a variable declaration is.

 

[pete]

If you want the cheap hack solution that probably doesn't satisfy your
professor very much but is very good for large arrays of a limited,
fixed number of entries, do a websearch on "Counting Sort".

/* BEGIN counting.c */

#include <stdio.h>

#define LETTERS "RBWWBBRWWRRWRBW"

void RWB_sort(char *array, size_t n);

int main(void)
{
char array[] = LETTERS;

puts(array);
RWB_sort(array, sizeof array - 1);
puts(array);
return 0;
}

void RWB_sort(char *array, size_t n)
{
size_t count[3] = {0};

while (n-- != 0) {
++count[(array[n] == 'W') + 2 * (array[n] == 'B')];
}
while (count[0]-- != 0) {
array[++n] = 'R';
}
while (count[1]-- != 0) {
array[++n] = 'W';
}
while (count[2]-- != 0) {
array[++n] = 'B';
}
}

/* END counting.c */

For a C solution, try qsort().

/* BEGIN q.c */

#include <stdio.h>
#include <stdlib.h>

#define LETTERS "RBWWBBRWWRRWRBW"

int compar(const void *arg1, const void *arg2);

int main(void)
{
char array[] = LETTERS;

puts(array);
qsort(array, sizeof array - 1, sizeof *array, compar);
puts(array);
return 0;
}

int compar(const void *arg1, const void *arg2)
{
int one = (*(char *)arg1 == 'W') + 2 * (*(char *)arg1 == 'B');
int two = (*(char *)arg2 == 'W') + 2 * (*(char *)arg2 == 'B');

return two > one ? -1 : two != one;
}

/* END q.c */

 

[Ian Malone]

Does anyone here understand the part:

char 'R'=1;
char 'W'=2;
char 'B'=3;

This has no meaning in C, at least not the meaning the author intended.
First, the syntax error is you cannot quote a variable name. In this
case the C compiler sees an attempt to declare the variables R, W and B
and throws out an error when it sees the variable names quoted.

> You don't seem to understand what a variable declaration is.

The OP is trying to set up a lookup table. While they may have
misunderstood variable declarations they have really misunderstood
character literals.

For the OPs benefit:
The compiler interprets 'R', 'W', 'X' as a number (in fact an int
within the range of char). The exact mapping is not specified,
it is often ASCII but not always. Certain things like the relative
order of the decimal digits '0', '1', '2' etc. are specified.
What you have written is a little like doing:
char 42 = 0; //Number chosen at random.

Whether you write your own sort or use qsort as suggested elsewhere,
what you are trying to do is map from the values of 'R', 'W' and 'B'
to the desired order in the sort. There are a number of ways of
doing this. You could allocate a sufficiently large array and then
do:
lookup['R'] = 0;
lookup['W'] = 1;
lookup['B'] = 2;
So when you read in a character to char x, lookup[x] (no quotes),
translates that character's representation into its order in the sort.

Alternatively, for a short and simple number of choices a switch
statement will do.

Remember 'R' and friends are just numbers to the compiler:
switch (x) {
case 'R':
lookup = 0;
break;
case 'W':
lookup = 1;
break;
case 'B':
lookup = 2;
break;
default:
lookup = -1;
}
/* Where x is the character you want to lookup, and lookup is an int */

 

[David Resnick]

my question is is there any simple solution to this problem. i been
doing this the whole day. cant get it work

How about this algorithm then. It isn't general purpose, but it works
well for the
problem as defined:

1) Make one pass through the input string, counting up the Rs, Ws, and
Bs
2) overwrite the original array, using a loop for each letter, and NOT
resetting
the array index in between

-David

 

[Skarmander]

How about this algorithm then. It isn't general purpose, but it works
well for the
problem as defined:

1) Make one pass through the input string, counting up the Rs, Ws, and
Bs
2) overwrite the original array, using a loop for each letter, and NOT
resetting
the array index in between

Here's an implementation you shouldn't use, because you'll probably be
asked to explain it (and it doesn't use swaps, which seems to be
required by the problem statement).

int r = 0, w = 0;
int i;

for (i = 0; letters; ++i) {
switch (letters) {
case 'R': ++r;
case 'W': ++w;
}
}
while (i != w) letters[--i] = 'B';
while (i != r) letters[--i] = 'W';
while (i != 0) letters[--i] = 'R';

S.

 

[Netocrat]

How about this algorithm then. It isn't general purpose, but it works
well for the
problem as defined:

1) Make one pass through the input string, counting up the Rs, Ws, and
Bs
2) overwrite the original array, using a loop for each letter, and NOT
resetting
the array index in between

Here's an implementation you shouldn't use, because you'll probably be
asked to explain it (and it doesn't use swaps, which seems to be
required by the problem statement).

int r = 0, w = 0;
int i;

for (i = 0; letters; ++i) {
switch (letters) {
case 'R': ++r;
case 'W': ++w;
}
}
while (i != w) letters[--i] = 'B';
while (i != r) letters[--i] = 'W';
while (i != 0) letters[--i] = 'R';

Neat. Here's an alternative that avoids some increments of w and uses
memset instead of while loops - probably no more efficient for small
strings like this, but likely it would be for large strings.

#include <stdio.h>
#include <string.h>

int main(void)
{
int r = 0, w = 0;
int i;
char letters[] = "RBWWBBRWWRRWRBW";

puts(letters);
for (i = 0; letters; ++i) {
switch (letters) {
case 'R': ++r;
break;
case 'W': ++w;
}
}
memset(letters , 'R', r);
memset(letters + r , 'W', w);
memset(letters + r + w, 'B', i - r - w);

puts(letters);
return 0;
}

 

[Christopher Benson-Manica]

1) Make one pass through the input string, counting up the Rs, Ws, and
Bs
2) overwrite the original array, using a loop for each letter, and NOT
resetting
the array index in between

You can make it work for upper case ASCII letters...

void sort( char *str ) {
unsigned int counts[26]={ 0 };
char *cp=str;
unsigned int idx, jdx;
while( *cp ) {
assert( isalpha(*cp) );
counts[ toupper(*cp)-'A' ]++;
cp++;
}
for( idx=0; idx < sizeof counts/sizeof *counts; idx++ ) {
for( jdx=0; jdx < counts[idx]; jdx++ ) {
*str++='A'+jdx;
}
}
}

 

[David Resnick]

You can make it work for upper case ASCII letters...

I was just proposing a (simpler) way for the OP to do his homework,
assuming he' d have to write it himself

void sort( char *str ) {
unsigned int counts[26]={ 0 };
char *cp=str;
unsigned int idx, jdx;
while( *cp ) {
assert( isalpha(*cp) );
counts[ toupper(*cp)-'A' ]++;

The above two is/to calls should be cast to (unsigned char).
Also, the assumption that A-Z are contiguous, while generally correct,
is not portable (I think in EBCDIC they are not).

cp++;
}
for( idx=0; idx < sizeof counts/sizeof *counts; idx++ ) {
for( jdx=0; jdx < counts[idx]; jdx++ ) {
*str++='A'+jdx;

I liked someone elses suggestion of memset for this.

-David

 

[Christopher Benson-Manica]

I was just proposing a (simpler) way for the OP to do his homework,
assuming he'd have to write it himself

Well, the code I posted isn't going to work unless OP at least figures
out some elementary things about it. (These homework posters probably
don't follow the thread this long anyway.)

assert( isalpha(*cp) );
counts[ toupper(*cp)-'A' ]++;

The above two is/to calls should be cast to (unsigned char).

Hm, and now I remember this same issue having come up just recently.
A pity I didn't remember it. :-(

Also, the assumption that A-Z are contiguous, while generally correct,
is not portable (I think in EBCDIC they are not).

I did state that the method worked for ASCII, which of course may not
be good enough for OP.

I liked someone elses suggestion of memset for this.

Me too, I noticed it afterward.

 

[Skarmander]

You can make it work for upper case ASCII letters...

<snip>

Here's the generic version, that makes no assumption about the character
set or collation order used, but is slower.

The next step would be to introduce hashing. Since the idea is that the
input range is small and constant, you can compute a minimal perfect
hash and use this, which will beat strchr(). This is left as an exercise
for the reader.

Although at this point you should probably consider a generic sorting
function anyway...


const char letters[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void sort(char* str) {
size_t counts[sizeof letters] = {0};
const char* cp;
size_t i;

for (cp = str; *cp; ++cp) {
const char* b = strchr(letters, *cp);
assert(b != NULL);
++counts[b - letters];
}
for (i = 0; i != sizeof letters; ++i) {
memset(str, letters, counts);
str += counts;
}
}

S.