HELP ME on Sorting Characters.

[Chris Torek]

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

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

 

[Bail]

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

 

[pete]

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.

 

[Bail]

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

 

[Bail]

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

 

[pete]

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]

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);
}
}
}

 

[Bail]

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

 

[pete]

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