K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library. I'm trying to implement the first,
which is in §4.10.
I think I'm pretty close with this:
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right)
return;
swap (v, left, (left + right)/2);
last = left;
for (i = left+ 1; i <= right; i++)
if (v[i] < v[left])
swap (v, ++last, i);
swap(v, left, last);
qsort(v, left, last - 1);
qsort(v, last + 1, right);
}
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
#include <stdio.h>
#define size 9
int main(void)
{
int m[size], i;
for (i=0; i < size; ++ i)
{
m[i] = i - size;
printf(" %d \n ", m[i]);
}
qsort (m[], 0, size - 1);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);
return 0;
}
// gcc -o sort c5.c
gcc objects with:
F:\gfortran\sou rce>gcc -o sort c5.c
c5.c: In function 'main':
c5.c:42: error: expected expression before ']' token
If I count correctly, this is the qsort call. I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
I guess that's question one. The other is how to call the stdlib version
of qsort, whose syntax is given in appdx B5:
void qsort(void *base, size_t n, size_t size,
int (*cmp)(const void *, const void *)
Beautiful night here in New Mexico. I can hear and even smell the state
fair. cheers,
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
Sep 9 '08
61  5863 
Richard wrote:
"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:
>Ron Ford wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
You are comparing the pointers, not the values they point to.
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);
}
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
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);
}
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
Joachim Schmitz wrote:
Richard wrote:
>"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:
>>Ron Ford wrote:
On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
>
You are comparing the pointers, not the values they point to.
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);
}
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
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);
}
Might overflow. The following should fix that:
int mycmp(const void *a, const void *b)
{
return (*(int *)a)>(*(int *)b)-(*(int *)a)<(*(int *)b));
}
Without the superfluos last )...
Richard wrote:
Richard<rg****@ gmail.comwrites :
>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);
}
other than the obvious typo of the variable names course ...
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
On Sep 13, 4:49 pm, Ralf Damaschke <rws...@gmx.dew rote:
Richard wrote:
Richard<rgr...@ gmail.comwrites :
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);
}
other than the obvious typo of the variable names course ...
It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).
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.
On Fri, 12 Sep 2008 21:55:18 -0700, Barry Schwarz posted:
On Fri, 12 Sep 2008 14:28:30 -0600, Ron Ford <ro*@example.in valid>
wrote:
>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
>>You are comparing the pointers, not the values they point to.
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);
}
>>>>
Do I need casts on a and b?
Not only casts but a dereference also. You had both in the original
code. Why did you remove them?
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
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.
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 >.
>>Furthermore , the library qsort claims to sort any datatype. Do they all
admit of orderings as do ints where '>' and '<' are well defined?
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...)
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\sou rce>gcc -o sort -Wall -std=c99 c9.c
F:\gfortran\sou rce>sort
Constantinople
14
ttspoonnnlieaC
F:\gfortran\sou rce>
Does that look right?
--
For every complex problem there is an answer that is clear, simple, and
wrong.
H. L. Mencken
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:
Ron Ford wrote:
>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:
>>On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
>>You are comparing the pointers, not the values they point to.
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);
}
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
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\sou rce>gcc -o sort -Wall -std=c99 c10.c
F:\gfortran\sou rce>sort
Constantinople
14
Caeilnnnoopstt
F:\gfortran\sou rce>
Without knowing better, I'd say I know better now.
--
Puritanism. The haunting fear that someone, somewhere, may be happy.
H. L. Mencken
Richard wrote:
Whats wrong with merely
>>
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...
There are about (2 * INT_MAX) situations,
where the result is undefined.
Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.
--
pete
pete said:
Richard wrote:
>Whats wrong with merely
>>>
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...
There are about (2 * INT_MAX) situations,
where the result is undefined.
Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.
I agree with your reasoning but not with your mathematics.
Let's take, for example, a simple four-bit int (with INT_MIN being -INT_MAX
- 1). Sure, it's non-conforming, but it illustrates the point and keeps
the arithmetic simple.
INT_MAX is 7. UB is invoked when the values are:
7 and any of -1, -2, -3, -4, -5, -6, -7, -8
6 and any of -2, -3, -4, -5, -6, -7, -8
5 and any of -3, -4, -5, -6, -7, -8
4 and any of -4, -5, -6, -7, -8
3 and any of -5, -6, -7, -8
2 and any of -6, -7, -8
1 and any of -7, -8
0 and -8
so it does seem that the number of UB cases is S(n + 1) where n is the
value of INT_MAX and S(n) = n(n+1)/2.
For an INT_MAX of 32767, for example, the number of UB cases is 536854528,
which is 16384 * INT_MAX, not 2 * INT_MAX.
--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
On Sun, 14 Sep 2008 00:15:18 +0000, Richard Heathfield posted:
pete said:
>Richard wrote:
>>Whats wrong with merely
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
other than the obvious typo of the variable names course ...
There are about (2 * INT_MAX) situations,
where the result is undefined.
Example:
if (*(int *)p2) equals INT_MAX
and (*(int *)p1) equals (-1),
then your program becomes meaningless.
I agree with your reasoning but not with your mathematics.
Let's take, for example, a simple four-bit int (with INT_MIN being -INT_MAX
- 1). Sure, it's non-conforming, but it illustrates the point and keeps
the arithmetic simple.
INT_MAX is 7. UB is invoked when the values are:
7 and any of -1, -2, -3, -4, -5, -6, -7, -8
6 and any of -2, -3, -4, -5, -6, -7, -8
5 and any of -3, -4, -5, -6, -7, -8
4 and any of -4, -5, -6, -7, -8
3 and any of -5, -6, -7, -8
2 and any of -6, -7, -8
1 and any of -7, -8
0 and -8
so it does seem that the number of UB cases is S(n + 1) where n is the
value of INT_MAX and S(n) = n(n+1)/2.
For an INT_MAX of 32767, for example, the number of UB cases is 536854528,
which is 16384 * INT_MAX, not 2 * INT_MAX.
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.
--
It is now quite lawful for a Catholic woman to avoid pregnancy by a resort
to mathematics, though she is still forbidden to resort to physics or
chemistry.
H. L. Mencken
Ron Ford said:
Richard Heathfield posted:
>pete said:
<snip>
>>>
There are about (2 * INT_MAX) situations,
where the result is undefined. [...]
>I agree with your reasoning but not with your mathematics.
<snip>
I agree with your mathematics but not your calculation.
Touche'. :-)
Maybe they serve coffee before service in the Continent.
During. I take it you've never heard of cafe church?
--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999 This thread has been closed and replies have been disabled. Please start a new discussion. |
