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\source>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  5749 
On Sun, 14 Sep 2008 15:21:37 +0200, Joachim Schmitz posted:
Ron Ford wrote:
>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.invalid>
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;
}
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
Nonsense, the possibility of overflow occurs when you return a number that
is the difference of the inputs, and it's completely unnecessary. See
Heathfield's analysis in this thread.
When you return a number that is necessarily 1, -1 or 0, how would it
overflow on a system with more than one bit bytes?
The critical thing you need here is the compare variable !=a or b, and its
inclusion was something I picked up from Glen Hermannsfeldt in c.l.f.:
integer function compare(i1,i2)
compare=0
if(i1>i2) compare=1
if(i1<i2) compare=-1
return
end
The necessity of the compare variable here is like the necessity of temp in
a reasonable swap.
--
No one in this world has ever lost money by underestimating the
intelligence of the great masses of the plain people. Nor has anyone ever
lost public office thereby.
H. L. Mencken
On Sun, 14 Sep 2008 07:30:25 +0000, Richard Heathfield posted:
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'. :-)
I think what you've shown is that you hit UB with just about an eighth of
the cases. There's 2 *INT_MAX + 1 integers, if INT_MIN = -INT_MAX. a
vector populated by two ints would then have (2*IM+1)**2 possiblities,
which is close to 4*IM**2. UB happens S(n+1) times=m(m+1)/2=(n+1)(n+2)/2
where n = IM. That's close to IM**2 /2. Their ratio is eight to one.
I can't think of a theoretical justifcation for why one eighth is the magic
ratio here.
>
>Maybe they serve coffee before service in the Continent.
During. I take it you've never heard of cafe church?
No. I hope for your sake that it's fundamentally different than the
fundies we have around here. I actually made it to services, and it was
all about forgiveness today, but I cannot find forgiveness for these
neocons. Are you supposed to forgive the robbers and usurpers who have
tagged you for seven years, and will continue to do so in the future? I'll
forgive Cheney when he's in Leavenworth or the Haag. (or hell)
--
We must be willing to pay a price for freedom.
H. L. Mencken
Ron Ford <ro*@example.invalidwrites:
[...]
The critical thing you need here is the compare variable !=a or b, and its
inclusion was something I picked up from Glen Hermannsfeldt in c.l.f.:
integer function compare(i1,i2)
compare=0
if(i1>i2) compare=1
if(i1<i2) compare=-1
return
end
The necessity of the compare variable here is like the necessity of temp in
a reasonable swap.
No, the compare variable is necessary because of the way functions
work in Fortran. C's return statement lets you return a value; you
don't have to store that value in a variable (though of course you
can).
In C, I'd consider any of the following to be reasonable:
if (i1 < i2) {
return -1;
}
elsif (i1 i2) {
return 1;
}
else {
return 0;
}
or:
int result = 0;
if (i1 < i2) {
result = -1;
}
if (i1 i2) {
result = 1;
}
return result;
or:
return (i1 i2) - (i1 < i2);
The latter is admittedly tricky. If you think it's *too* tricky, I
won't argue with you.
--
Keith Thompson (The_Other_Keith) 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"
Ron Ford <ro*@example.invalidwrites:
[...]
No. I hope for your sake that it's fundamentally different than the
fundies we have around here. I actually made it to services, and it was
all about forgiveness today, but I cannot find forgiveness for these
neocons. Are you supposed to forgive the robbers and usurpers who have
tagged you for seven years, and will continue to do so in the future? I'll
forgive Cheney when he's in Leavenworth or the Haag. (or hell)
Can we *please* avoid discussing politics here?
--
Keith Thompson (The_Other_Keith) 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 Sun, 14 Sep 2008 14:37:10 -0700, Keith Thompson posted:
Ron Ford <ro*@example.invalidwrites:
[...]
>The critical thing you need here is the compare variable !=a or b, and its
inclusion was something I picked up from Glen Hermannsfeldt in c.l.f.:
integer function compare(i1,i2)
compare=0
if(i1>i2) compare=1
if(i1<i2) compare=-1
return
end
The necessity of the compare variable here is like the necessity of temp in
a reasonable swap.
No, the compare variable is necessary because of the way functions
work in Fortran. C's return statement lets you return a value; you
don't have to store that value in a variable (though of course you
can).
§1.8 K&R speaks to this, specifically naming fortran. I haven't quite
sorted this out, and I find Cspeak and Fortranspeak difficult to combine in
this context.
F03 promises C interoperability. One of the things you can do is
explicitly "call by value." Unfortunately, no f03 compiler exists.:-(
>
In C, I'd consider any of the following to be reasonable:
if (i1 < i2) {
return -1;
}
elsif (i1 i2) {
return 1;
}
else {
return 0;
}
or:
int result = 0;
if (i1 < i2) {
result = -1;
}
if (i1 i2) {
result = 1;
}
return result;
or:
return (i1 i2) - (i1 < i2);
The latter is admittedly tricky. If you think it's *too* tricky, I
won't argue with you.
I think this goes to legibility. Good code documents itself. There's no
significant performance loss/gain here, but in the latter scenario, it's
harder to see the zero outcome in particular. Add a bunch of pointers and
casts, and then you open the door for UB.
Of course, you weren't arguing.
--
Love is the delusion that one woman differs from another.
H. L. Mencken
Keith Thompson said:
Ron Ford <ro*@example.invalidwrites:
[...]
>No. I hope for your sake that it's fundamentally different than the
fundies we have around here. I actually made it to services, and it was
all about forgiveness today, but I cannot find forgiveness for these
neocons. Are you supposed to forgive the robbers and usurpers who have
tagged you for seven years, and will continue to do so in the future?
I'll
forgive Cheney when he's in Leavenworth or the Haag. (or hell)
Can we *please* avoid discussing politics here?
Well, yes, of course, but until you chipped in, I had no idea he /was/
talking about politics. He hadn't made this clear. Now that you mention
it, I can *guess* what "neocons" means, although I could easily be wrong
in my guess. And as for the references to "Leavenworth" and "the Haag", I
presume that they are somewhat equivalent to the Chiltern Hundreds but,
again, I could easily be wrong about that.
Back to topic: the observation that the ratio of UB additions of ints to
the total number of additions of ints is (approximately)
((INT_MAX * INT_MAX) / 2) / ((INT_MAX * 2) * (INT_MAX * 2)) =
(1/2) / (2 * 2) =
1/8
is interesting for two reasons: (1) it's so high, and (2) it's a constant
ratio (to a first approximation, anyway), regardless of the value of
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
In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.orgwrote:
>Ron Ford <ro*@example.invalidwrites:
[...]
>No. I hope for your sake that it's fundamentally different than the
fundies we have around here. I actually made it to services, and it was
all about forgiveness today, but I cannot find forgiveness for these
neocons. Are you supposed to forgive the robbers and usurpers who have
tagged you for seven years, and will continue to do so in the future? I'll
forgive Cheney when he's in Leavenworth or the Haag. (or hell)
Can we *please* avoid discussing politics here?
Don't see how. We discuss religion all the time.
And, in modern day America, politics and religion are intimately bound
together. Deal with it.
Ben Bacarisse said:
Richard Heathfield <rj*@see.sig.invalidwrites:
<snip>
>Back to topic: the observation that the ratio of UB additions of ints to
the total number of additions of ints is (approximately)
((INT_MAX * INT_MAX) / 2) / ((INT_MAX * 2) * (INT_MAX * 2)) =
(1/2) / (2 * 2) =
1/8
is interesting for two reasons: (1) it's so high, and (2) it's a
constant ratio (to a first approximation, anyway), regardless of the
value of INT_MAX.
Unless I am mistaken about your method it is high, in part, because you
count every addition twice: a+b and b+a.
Rats. I meant subtractions.
--
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 9 Sep, 21:00, Ron Ford <r...@example.invalidwrote:
>>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.
In article <5a**********************************@d1g2000hsg.g ooglegroups.com>
Nick Keighley <ni******************@hotmail.comwrote:
>I don't understand what "modify calls to qsort()" means.
This was in a side discussion about whether compilers are allowed
to recognize (and modify) calls to "standard library" functions.
We have examples of compilers that *do* this. Under gcc, with
certain invocations, this:
#include <stdio.h>
int main(void) {
printf("hello world\n");
return 0;
}
compiles to code that links with the puts() routine, not the printf()
routine. Clearly there is a call to printf(), but in fact there
is a call to puts(). The compiler has modified the source code,
so that there is no call to printf() in the object code.
Similarly, compilers may "inline" calls to memcpy() (many do),
sqrt() (some do), and so on. So if you, as a C programmer simply
using some implementation(s), attempt to do tricky things "behind
the back" of your implementation -- such as provide your own private
printf() or sqrt() or memcpy() -- you may get ambushed by the
compiler.
The main take-away lesson for the C programmer is, or at least
should be, "when you write a sort routine, do not call it qsort()".
Use some other name, such as "Hoare_QuickSort()" for instance.
Then, even if some fancy compiler recognizes and modifies calls to
qsort() -- just as gcc modifies calls to printf() and memcpy() --
it will not affect *your* code, because you did not use the name
"qsort". (In this respect, K&R, even K&R2, are doing a bit of a
disservice. To be fair, the original book was written during the
"wild west days of C" as it were, when C was whatever Dennis's
compiler did, and even the second edition predated the C standard.
The new standard gave compiler-writers more options than Dennis
had perhaps intended originally.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html
In article <ga*********@online.de>,
Joachim Schmitz <jo**@schmitz-digital.dewrote:
>vi******@gmail.com wrote:
>On Sep 12, 12:07 am, Ron Ford <r...@example.invalidwrote:
>>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
What JoJo is trying to say is this: Get rid of those crippling options
in the command line! Don't use options whose only function is to
cripple your compiler (meaning: -ansi and -pedantic).
wrote:
On Sep 14, 6:56 pm, Ralf Damaschke <rws...@gmx.dewrote:
><no name givenwrote:
I'm curious, why "<no name given>"?
Above you see what my newsreader produced for the attribution
from the name in your "From:" header .
I felt that this looks too obscure and added a placeholder to
where the name should have been.
-- Ralf
Ralf Damaschke wrote:
wrote:
>On Sep 14, 6:56 pm, Ralf Damaschke <rws...@gmx.dewrote:
>><no name givenwrote:
I'm curious, why "<no name given>"?
Above you see what my newsreader produced for the attribution
from the name in your "From:" header .
I felt that this looks too obscure and added a placeholder to
where the name should have been.
In my own newsreader, and when I use Google groups, his From: line is
properly filled in. This thread has been closed and replies have been disabled. Please start a new discussion. |
