By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,937 Members | 1,176 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,937 IT Pros & Developers. It's quick & easy.

HELP ME on Sorting Characters.

P: n/a
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[i]> 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;
}

Nov 15 '05 #1
Share this Question
Share on Google+
28 Replies


P: n/a
fb
Ba********@gmail.com wrote:
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
Nov 15 '05 #2

P: n/a
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?

Nov 15 '05 #3

P: n/a

Ba********@gmail.com wrote:
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[i]> 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

Nov 15 '05 #4

P: n/a
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[i]);
} // 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[i] > big ) {
big = array[i];
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;

Nov 15 '05 #5

P: n/a
Ba********@gmail.com wrote:
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.


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
Nov 15 '05 #6

P: n/a

Ba********@gmail.com wrote:
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[i]);
'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[i] > big ) {
big = array[i];
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

Nov 15 '05 #7

P: n/a
thats what i am doing. sorting the dutch national flag. anyway soultion?

Nov 15 '05 #8

P: n/a

Bailey....@gmail.com wrote:
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.

Nov 15 '05 #9

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

Nov 15 '05 #10

P: n/a

Ba********@gmail.com wrote:
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[i]> 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.

Nov 15 '05 #11

P: n/a
Richard Bos wrote:

Ba********@gmail.com wrote:
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.
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 */

--
pete
Nov 15 '05 #12

P: n/a
sl*******@gmail.com wrote:
Ba********@gmail.com wrote:
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.

<snip>
}


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 */

--
imalone
Nov 15 '05 #13

P: n/a

Ba********@gmail.com wrote:
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

Nov 15 '05 #14

P: n/a
David Resnick wrote:
Ba********@gmail.com wrote:
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

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]; ++i) {
switch (letters[i]) {
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.
Nov 15 '05 #15

P: n/a
On Mon, 07 Nov 2005 16:32:33 +0100, Skarmander wrote:
David Resnick wrote:
Ba********@gmail.com wrote:
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

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]; ++i) {
switch (letters[i]) {
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]; ++i) {
switch (letters[i]) {
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;
}

--
http://members.dodo.com.au/~netocrat
Nov 15 '05 #16

P: n/a
David Resnick <ln********@gmail.com> wrote:
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;
}
}
}

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Nov 15 '05 #17

P: n/a
Christopher Benson-Manica wrote:
David Resnick <ln********@gmail.com> wrote:
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...


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

Nov 15 '05 #18

P: n/a
David Resnick <ln********@gmail.com> wrote:
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.

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
Nov 15 '05 #19

P: n/a
Christopher Benson-Manica wrote:
David Resnick <ln********@gmail.com> wrote:

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

<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[i], counts[i]);
str += counts[i];
}
}

S.
Nov 15 '05 #20

P: n/a
>Christopher Benson-Manica wrote:
assert( isalpha(*cp) );
counts[ toupper(*cp)-'A' ]++;

In article <11**********************@f14g2000cwb.googlegroups .com>
David Resnick <ln********@gmail.com> wrote:The above two is/to calls should be cast to (unsigned char).
Technically I think you can get away with just one: if isalpha() says
it is (and you are in the C locale), *cp itself must be nonnegative
even if plain "char" is signed.

Of course, if one is not in the C locale, there are actual cases
where isalpha() is true but *cp is negative:

#include <ctype.h>
#include <locale.h>
#include <stdio.h>

int main(void) {
char c, *cp = &c;

setlocale(LC_CTYPE, "ISO8859-1");
*cp = 0xc4;
if (isalpha((unsigned char)*cp))
printf("%c (%d) is alphabetic\n", *cp, *cp);
return 0;
}

Uppercase A-umlaut (code 0xc4) is indeed alphabetic in ISO-Latin-1,
but is negative on many machines; when I run this, I get:

(-60) is alphabetic

There is also one character (German eszet) that has no uppercase
equivalent, so that toupper() leaves it lowercase.
Also, the assumption that A-Z are contiguous, while generally correct,
is not portable (I think in EBCDIC they are not).


Indeed, in EBCDIC they are not: there is a gap between 'I' and 'J',
and another between 'R' and 'S'.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 15 '05 #21

P: n/a
can some one explain to me in details how the C soultion qsort( ) work
in here.
/* 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 */

Nov 15 '05 #22

P: n/a
Bail wrote:

can some one explain to me in details how the C soultion qsort( ) work
in here.

/* BEGIN q.c */

#include <stdio.h>
That's for puts.
#include <stdlib.h>
That's for qsort.

#define LETTERS "RBWWBBRWWRRWRBW"
LETTERS expands to an identifier of an array of char.
int compar(const void *arg1, const void *arg2);
That's the protoype for a qsort compar function.
All qsort compar functions have those same two argument types.
int main(void)
{
char array[] = LETTERS;
array contains a string.
The array which is to be sorted, is the part of
the string that does not include the null terminator.
puts(array);
The null terminator isn't sorted with the rest of the string,
so puts is an easy way to display it.
qsort(array, sizeof array - 1, sizeof *array, compar);
That's also why it's (sizeof array - 1) instead of (sizeof array).
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');
"one" (meaning the array element corresponding to arg1)
takes a value of either 0,1, or 2,
depending on whether (*(char *)arg1) is 'R', 'W', or 'B'.

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

}
If the elements are in order, return -1.
If the elements are in reverse order return 1.
If the elements equal, return 0.
/* END q.c */


Ask, if you have further question.

--
pete
Nov 15 '05 #23

P: n/a
can some one explain to me the C solution qsort( ). i dont get how that
function works.

Nov 15 '05 #24

P: n/a
can some one explain to me the C solution qsort( ). i dont get how that
function works.

Nov 15 '05 #25

P: n/a
Bail wrote:

can some one explain to me the C solution qsort( ).
i dont get how that function works.


N869
7.20.5.2 The qsort function
Synopsis
[#1]
#include <stdlib.h>
void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
Description
[#2] The qsort function sorts an array of nmemb objects, the
initial element of which is pointed to by base. The size of
each object is specified by size.
[#3] The contents of the array are sorted into ascending
order according to a comparison function pointed to by
compar, which is called with two arguments that point to the
objects being compared. The function shall return an
integer less than, equal to, or greater than zero if the
first argument is considered to be respectively less than,
equal to, or greater than the second.
[#4] If two elements compare as equal, their order in the
resulting sorted array is unspecified.
Returns
[#5] The qsort function returns no value.

Here's a qsort style function implemented with
a Shellsort algorithm:

void q_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t bytes;
unsigned char *array, *after, *i, *j, *k, *p1, *p2, *end, swap;

array = base;
after = nmemb * size + array;
if (nmemb > (size_t)-1 / 3 - 1) {
nmemb = nmemb / 3 - 1;
} else {
nmemb = (nmemb * 3 + 1) / 7;
}
while (nmemb != 0) {
bytes = nmemb * size;
i = bytes + array;
do {
j = i - bytes;
if (compar(j, i) > 0) {
k = i;
do {
p1 = j;
p2 = k;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (bytes + array > j) {
break;
}
k = j;
j -= bytes;
} while (compar(j, k) > 0);
}
i += size;
} while (i != after);
nmemb = (nmemb * 3 + 1) / 7;
}
}

--
pete
Nov 15 '05 #26

P: n/a
pete wrote:
Here's a qsort style function implemented with
a Shellsort algorithm:


Here's a qsort style function implemented with
a simple selection sort algorithm which might be easier
to understand. It sorts the first element first,
then the next, until it gets to the end.

void slsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *first, *middle;
size_t tail_memb;
unsigned char *p1, *p2, *end, swap;

for (array = base; nmemb-- > 1; array += size) {
middle = first = array + size;
tail_memb = nmemb;
while (--tail_memb != 0) {
middle += size;
if (compar(first, middle) > 0) {
first = middle;
}
}
if (compar(array, first) > 0) {
p1 = array;
p2 = first;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
}
}
}

--
pete
Nov 15 '05 #27

P: n/a
i have a question. instead of #define LETTERS "RBWWBBRWWRRWRBW" how
can i change the function so that let the user input any number of R's
W's and B's then sort it out.

something like?
#define Letters 81

void getChars( char *flag) {

Printf(" Please enter R's W's or B's only!");
scanf("%c", &flag);
}
so how do i call the function in the main, so that it can sort it out

Nov 15 '05 #28

P: n/a
Bail wrote:

i have a question. instead of #define LETTERS "RBWWBBRWWRRWRBW" how
can i change the function so that let the user input any number of R's
W's and B's then sort it out.

something like?
#define Letters 81

void getChars( char *flag) {

Printf(" Please enter R's W's or B's only!");
scanf("%c", &flag);
}

so how do i call the function in the main, so that it can sort it out


/*
** If rc equals 0, then an empty line was entered
** and the array contains garbage.
** If rc equals EOF, then the end of file was reached.
** If rc equals 1, then there is a string in array.
/*
/* BEGIN new.c */

#include <stdio.h>

#define LENGTH 30
#define str(x) # x
#define xstr(x) str(x)

int main(void)
{
int rc;
char array[LENGTH + 1];

fputs("Enter a string with spaces:", stdout);
fflush(stdout);
rc = scanf("%" xstr(LENGTH) "[^\n]%*[^\n]", array);
if (!feof(stdin)) {
getchar();
}
while (rc == 1) {
printf("Your string is:%s\n\n"
"Hit the Enter key to end,\nor enter "
"another string to continue:", array);
fflush(stdout);
rc = scanf("%" xstr(LENGTH) "[^\n]%*[^\n]", array);
if (!feof(stdin)) {
getchar();
}
}
return 0;
}

/* END new.c */

--
pete
Nov 15 '05 #29

This discussion thread is closed

Replies have been disabled for this discussion.