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 
On Wed, 10 Sep 2008 02:44:37 -0700 (PDT), Nick Keighley posted:
could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.
On 9 Sep, 21:00, Ron Ford <r...@example.i nvalidwrote:
>On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
>>On 9 Sep, 06:30, Ron Ford <r...@example.i nvalidwrote:
>>>K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
>>note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.
I think there's two issues here. *An implementation could modify the call
to qsort. *Chris Torek says this about that:
%- That said, I do not know of any C implementations that modify calls
%- to qsort(). *Of course, this does not guarantee that none exist.
%- (Among other things, to cross comp.lang.c threads a bit, I have
%- never seen or used a [full] C99 implementation. *Perhaps one of
%- those -- several are rumored to exist -- might substitute some
%- qsort() calls, for instance.
I don't understand what "modify calls to qsort()" means.
I'm appropriately uncomfortable trying to elaborate on what Chris, in a
slightly differing context, writes. I think the idea is that if you printf
the word "hi," your implementation could instead putchar h and i.
again, we don't seem to be speaking the same version of english.
You don't see what where? By "implement" you mean cut-and-paste?
If you cut and paste with a book, you destroy its future value.
"Implement" means making the necessary keystrokes to make code work.
>>go and reread about arrays. eg K&R page 29
I leafed through pp25-100 and didn't see it.
p29 of my k&R has a function called getline() which takes a char[]
argument. Just above that is main() which calls getline() on line 16.
This call uses the correct syntax.
The calls on pg 29 are for char arrays and have brackets. My error was
that I had to lose the brackets.
>
>>>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.
>>good. because it's wrong
No, it was the brackets on m in the qsort call that was the culprit on line
42.
Note the bit I commented on was "If I count correctly, this is the
qsort call."
So I told you the quicksort call was wrong, so where does the "No"
above come from?
--
NIck Keighley
"You fell victim to one of the classic blunders.
The most famous is 'Never get involved in a land war in Asia,' "
The error on line 42 no longer exists. It just occured to me that "don't
get in a land war in Asia" is precisely what the texans did.
--
What men value in this world is not rights but privileges. 7
H. L. Mencken
On Tue, 09 Sep 2008 18:26:41 -0700, Keith Thompson posted:
Ron Ford <ro*@example.in validwrites:
[...]
>The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>
?
Luck (arguably bad luck).
In C90, if you call a function with no visible declaration, the
compiler will assume that it returns int, and that it expects
arguments of the promoted types of the arguments you actually gave it.
If the generated code happens to work with the the actual function,
you can get what appear to be correct results. If not, arbitrarily
bad things can happen.
C99 dropped implicit int, so an attempt to call qsort with no visible
declaration would result in a mandatory diagnostic. But there are few
conforming C99 compilers yet.
But most compilers will warn you about such a call with the right
options. I advise you to find out what those options are for your
compiler, and get into the habit of using them.
Another possibility is that you might have included some other file
that directly or indirectly included <stdlib.h>. That would work, but
IMHO it's better style to have an explicit #include <stdlib.hin the
file that contains the qsort call.
Thanks, Keith. I thought I'd crank up the warnings and don't know what I'm
seeing.
F:\gfortran\sou rce>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:51: error: expected expression before '/' token
c6.c: At top level:
c6.c:58: error: expected identifier or '(' before '/' token
Lines 51 and 58 are comments. Just to see if they would work otherwise, I
compiled with no flags and was successful:
F:\gfortran\sou rce>gcc c6.c
issues no diagnostics. I thought it might be to lack of inclusion of
stdlib.h, but I get the same thing after I add it:
void qsort1(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);
qsort1(v, left, last - 1);
qsort1(v, last + 1, right);
}
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}
#include <stdio.h>
#include <stdlib.h>
#define size 9
int main(void)
{
int m[size], i;
for (i=0; i < size; ++ i)
{
m[i] = size - i;
printf(" %d \n ", m[i]);
}
qsort1 (m, 0, size - 1);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);
// call library qsort line 52
qsort(m, size, sizeof(int), mycmp);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);
return 0;
}
// gcc -o sort -Wall -pedantic -ansi c6.c line 58
F:\gfortran\sou rce>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:52: error: expected expression before '/' token
c6.c: At top level:
c6.c:59: error: expected identifier or '(' before '/' token
Is '//' not a kosher comment?
--
War will never cease until babies begin to come into the world with larger
cerebrums and smaller adrenal glands. 2
H. L. Mencken
On Sep 12, 12:07 am, Ron Ford <r...@example.i nvalidwrote:
Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
Ron Ford <ro*@example.in validwrites:
[...]
Is '//' not a kosher comment?
It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.
(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
--
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" vi******@gmail. com writes:
On Sep 12, 12:07 am, Ron Ford <r...@example.i nvalidwrote:
>Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
What on earth are you babbling about? // is a perfectly good comment
prefix.
On Thu, 11 Sep 2008 14:19:46 -0700 (PDT), vi******@gmail. com posted:
On Sep 12, 12:07 am, Ron Ford <r...@example.i nvalidwrote:
>Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
[comp.lang.c]
!delete From {vippstar}
--
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 Thu, 11 Sep 2008 15:06:41 -0700, Keith Thompson posted:
Ron Ford <ro*@example.in validwrites:
[...]
>Is '//' not a kosher comment?
It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.
(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
I'm promiscuous with syntax and compilers. Comments are the last thing I
remember; they're almost like comments. Is /* ...*/ the only legal C90
comment?
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
On Sep 12, 1:06 am, Keith Thompson <ks...@mib.orgw rote:
Ron Ford <r...@example.i nvalidwrites:
[...]
Is '//' not a kosher comment?
It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.
(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
For a while?! Here's a quote from Ron Ford:
Message-ID: <93************ *************** **@40tude.net>
These made great reading. It's been years since I've read Dan Pop.
Years. He reads Dan Pop, the standard too. (see the message) Yet, //
is a "kosher comment".
Here, in this article, <1l************ ***@example.inv alid>, he
correctly uses the // comment, and compiles with -std=c99.
Why did he choose to change it to -ansi -pedantic, while using //?
Wouldn't he remember that with -std=c99 it worked? Isn't that a hint
that it's a C99 feature?
Here's another article of his, <jk************ ***@example.inv alid>.
In this one, he seems quite confident to claim that // is indeed a
comment.
(He also suggests to look at the 7th chapter of K&R, though //
comments are not mentioned at all in K&R...)
Plus, the usual nonsense.
Keith, why do you still bother? It's your right to do so, if you want,
but it puzzles me.
On Fri, 12 Sep 2008 00:25:01 +0200, Richard posted: vi******@gmail. com writes:
>On Sep 12, 12:07 am, Ron Ford <r...@example.i nvalidwrote:
>>Is '//' not a kosher comment?
No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?
What on earth are you babbling about? // is a perfectly good comment
prefix.
I did a little reading for flags in gcc.pdf, and I think this is what I
wanted for when I didn't have stdlib included:
F:\gfortran\sou rce>gcc -o sort -Wall c6.c
c6.c: In function 'main':
c6.c:53: warning: implicit declaration of function 'qsort'
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?"
--
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
Ron Ford <ro*@example.in validwrites:
On Thu, 11 Sep 2008 15:06:41 -0700, Keith Thompson posted:
>Ron Ford <ro*@example.in validwrites:
[...]
>>Is '//' not a kosher comment?
It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.
(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)
I'm promiscuous with syntax and compilers. Comments are the last thing I
remember; they're almost like comments. Is /* ...*/ the only legal C90
comment?
Yes (though #if 0 ... #endif can serve a similar purpose).
--
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" This thread has been closed and replies have been disabled. Please start a new discussion. |
