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  5858 
Ron Ford <ro*@example.in validwrites:
[...]
I looked in stdlib.h and found the declaration for qsort for my
implementation.
_CRTIMP void __cdecl qsort(void*, size_t, size_t,
int (*)(const void*, const void*));
Does this suggest a better search for google to find the source for my
qsort implementation than "qsort.c gcc source?"
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.
--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
On Thu, 11 Sep 2008 15:07:10 -0600, Ron Ford <ro*@example.in valid>
wrote:
snip
>int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}
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.
--
Remove del for email
On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
>On Thu, 11 Sep 2008 19:05:28 -0700, Barry Schwarz posted:
>On Thu, 11 Sep 2008 15:07:10 -0600, Ron Ford <ro*@example.in valid>
wrote:
snip
>>>int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}
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.
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;
You are comparing the pointers, not the values they point to.
if (a b) compare = -1;
return (compare);
}
snip
>
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?
--
Remove del for email
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
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?
--
When a new source of taxation is found it never means, in practice, that
the old source is abandoned. It merely means that the politicians have two
ways of milking the taxpayer where they had one before. 8
H. L. Mencken
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.
>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.:-(
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.
>
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...)
--
Remove del for email vi******@gmail. com wrote:
On Sep 12, 12:07 am, Ron Ford <r...@example.i nvalidwrote:
>Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
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
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
"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);
}
Richard<rg****@ gmail.comwrites :
"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);
}
other than the obvious typo of the variable names course ...
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?
To not alter the OP's code too much. To not have more than one extit from
the function
Why do the second compare?
Because that wouldn't work in case both operands are equal
Also, is the gcc implementation not standard? Whats wrong with merely
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}
At least the syntax 8-)
Bye, Jojo This thread has been closed and replies have been disabled. Please start a new discussion. |
