K
Keith Thompson
Ron Ford said:
Yes (though #if 0 ... #endif can serve a similar purpose).
Yes (though #if 0 ... #endif can serve a similar purpose).
K
Keith Thompson
Ron Ford said:
gcc doesn't provide qsort; qsort is provided by your C library.
Depending on which system you're using, the source for your C
library's qsort implementation may or may not be available. If it is
available, I suggest asking in a newsgroup that deals with your
operating system.
B
Barry Schwarz
snip
qsort requires mycmp to return a negative, zero, or positive value
depending of the result of the comparison. Yours will return 0 for
both equality and "greater than". That should confuse the hell out of
qsort.
qsort requires mycmp to return a negative, zero, or positive value
depending of the result of the comparison. Yours will return 0 for
both equality and "greater than". That should confuse the hell out of
qsort.
R
Ron Ford
I thought this might address your criticism, but output says differently.
int mycmp(const void *a, const void *b)
{
int compare = 0;
if (a < b) compare = 1;
if (a > b) compare = -1;
return (compare);
}
F:\gfortran\source>gcc -o sort -Wall c8.c
F:\gfortran\source>sort
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
8
7
6
9
5
4
3
2
1
Do I need casts on a and b?
B
Barry Schwarz
You are comparing the pointers, not the values they point to.
Not only casts but a dereference also. You had both in the original
code. Why did you remove them?
R
Ron Ford
This seems right and behaves:
int mycmp(const void *a, const void *b)
{
int compare = 0;
if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a > *(const int *)b) compare = -1;
return (compare);
}
The short answer is that I don't understand them fully. In particular, I
dont understand the second asterisk in
*(const int *)a
.. The first dereferences what 'a' points to. The const int makes the
compiler believe it's an integer. The second is there because that was how
Nate formulated the original return, which I had to change to reflect three
cases instead of two, not because I know why.:-(
Furthermore, the library qsort claims to sort any datatype. Do they all
admit of orderings as do ints where '>' and '<' are well defined?
B
Barry Schwarz
1 - The first asterisk dereferences its operand which is not exactly
a. a is a void* and you cannot dereference it (because the resulting
type would be void which is a incomplete type that cannot be
completed).
2 - The only allowable operand for the dereference operator is a
pointer. That should be your clue that const int is not the type we
want here.
3 - When deciphering a declaration or cast, you go left to right until
there is a reason to stop. The only reason I can think of at the
moment is a right parenthesis. So the type of the cast is const int *
which is a pointer type that can be dereferenced.
The second one is there to avoid the exact problem you describe. You
cannot dereference an int but you can dereference a pointer to int.
The reason qsort can sort any **array** type is because you provide
the compare function. qsort will pass your compare function the
address of two elements (converted to void* because that is the
generic pointer type that can hold any type of address). Your compare
function must convert each pointer to void to the correct type for
your array elements, perform the compare, and return the appropriate
+/0/- value back to qsort so it can decide whether to swap the
elements or not. (You have almost complete freedom as to what the
word compare means in this context. You could compare the int values
as this code does. You could use the % operator and compare only the
units digits. You could compare absolute values and sort by magnitude
only, ignoring sign. If the array element is a struct type, you could
sort based on one or more elements. If the array element is a pointer
type, you could sort based on the pointer values (addresses) or on the
values the pointers point to...)
J
Joachim Schmitz
Not quite right. It is not a kosher comment in C90, which Ron is apparently
using (gcc -o sort -Wall -pedantic -ansi c6.c).
It is perfectly legal in C99 and a common extension in many compilers that
are not C99
Bye, Jojo
J
Joachim Schmitz
Ron said:
I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;
if (*p1 < *p2) compare = 1;
if (*p1 > *p2) compare = -1;
return compare;
}
Saves you all these nasty casts. It's less typing too.
Bye, Jojo
R
Richard
Joachim Schmitz said:
Why no else or simple returns? Why do the second compare?
Also, is the gcc implementation not standard? Whats wrong with merely
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
R
Richard
Richard said:
other than the obvious typo of the variable names course ...
J
Joachim Schmitz
Richard said:
To not alter the OP's code too much. To not have more than one extit from
the function
Because that wouldn't work in case both operands are equal
At least the syntax
Bye, Jojo
J
Joachim Schmitz
Richard said:
Might overflow. The following should fix that:
int mycmp(const void *a, const void *b)
{
return (*(int *)a)>(*(int *)b)-(*(int *)a)<(*(int *)b));
}
Bye, Jojo
J
Joachim Schmitz
Joachim said:
Without the superfluos last )...
R
Ralf Damaschke
Richard said:
It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).
-- Ralf
V
vippstar
6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.
R
Ron Ford
Thanks, Barry, for your generous response. I read it, slept on it (don't
tell my girlfriend) and think I get it. Let's see if I do:
1) a comes in as a void pointer, gets a const int * cast, which is
completable, is dereferenced, leaving a const int, which can be compared by
< and >.
I thought I would try my hand at another sort, and this seems to work:
int mycmp(const void *a, const void *b)
{
int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a > *(const char *)b) compare = -1;
return (compare);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
int m;
char s[] = "Constantinople";
printf (" %s \n", s);
m = strlen(s);
printf (" %d \n ", m);
qsort(s, m, sizeof(char), mycmp);
printf (" %s \n", s);
return 0;
}
// gcc -o sort -Wall -std=c99 c9.c
F:\gfortran\source>gcc -o sort -Wall -std=c99 c9.c
F:\gfortran\source>sort
Constantinople
14
ttspoonnnlieaC
F:\gfortran\source>
Does that look right?
R
Ron Ford
Thanks, jojo, yours is a cleaner and "better" version. I adapted it to a
charsort:
int mycmp(const void *a, const void *b)
{
int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a > *(const char *)b) compare = -1;
return (compare);
}
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;
if (*p1 < *p2) compare = -1;
if (*p1 > *p2) compare = 1;
return compare;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
int m;
char s[] = "Constantinople";
printf (" %s \n", s);
m = strlen(s);
printf (" %d \n ", m);
qsort(s, m, sizeof(char), mycmp2);
printf (" %s \n", s);
return 0;
}
// gcc -o sort -Wall -std=c99 c10.c
F:\gfortran\source>gcc -o sort -Wall -std=c99 c10.c
F:\gfortran\source>sort
Constantinople
14
Caeilnnnoopstt
F:\gfortran\source>
Without knowing better, I'd say I know better now.
R
Ron Ford
I agree with your mathematics but not your calculation.
S(n+1) is 32768 * 32769/2 = 536887296
, which is 16385 * INT_MAX.
As I've resolved to make it to church tomorrow, I'll cut out with C pretty
soon here and only have fifty percent chance of making it. How do you?
Maybe they serve coffee before service in the Continent.
J
Joachim Schmitz
Ron said:
Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
return (*p1 > *p2) - (*p1 < *p2);
}
Or with the casts:
int mycmp2(const void *a, const void *b)
{
return (*(const char *)a > *(const char *)b) - (*(const char *)a < *(const
char *)b);
}
but I like the former better.
Bye, Jojo