what type of sort is this?

[Lane Straatman]

void s_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t bytes;
unsigned char *array, *after, *i, *j, *k, *p1, *p2, *end, swap;

array = base;
after = nmemb * size + array;
if (nmemb (size_t)-1 / 4) {
nmemb /= 4;
} else {
nmemb = (nmemb * 3 + 1) / 7;
}
while (nmemb != 0) {
bytes = nmemb * size;
i = bytes + array;
do {
j = i - bytes;
if (compar(j, i) 0) {
k = i;
do {
p1 = j;
p2 = k;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (bytes + array j) {
break;
}
k = j;
j -= bytes;
} while (compar(j, k) 0);
}
i += size;
} while (i != after);
nmemb = (nmemb * 3 + 1) / 7;
}
/* end source */
What type of sort is this? It's working code that pete posted for
evaluating five card stud. How general is it? LS

[Eric Sosman]

Lane Straatman wrote:

void s_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
[... see up-thread ...]

What type of sort is this? It's working code that pete posted for
evaluating five card stud. How general is it? LS

1) This isn't really a C question, although it requires
the ability to read C source. comp.programming might be a
better forum for algorithmic issues.

2) At a quick glance, it looks like Shell's diminishing-
increment sort ("Shellsort"):

http://www.cs.princeton.edu/~rs/shell/index.html

--
Eric Sosman
es*****@acm-dot-org.invalid

[Lane Straatman]

"Eric Sosman" <es*****@acm-dot-org.invalidwrote in message
news:__******************************@comcast.com. ..

Lane Straatman wrote:

>void s_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
[... see up-thread ...]

What type of sort is this? It's working code that pete posted for
evaluating five card stud. How general is it? LS

1) This isn't really a C question, although it requires
the ability to read C source. comp.programming might be a
better forum for algorithmic issues.

I'm not so interested in the algorithmic properties but am interested in the
C. Before I read up on it after your post, I thought that they called it a
shell sort because of the way you might move a pea around with a shell as
magicians do. Apparently there's a guy named Shell.

It is an open question on its complexity. It is approximately O(4/3).

2) At a quick glance, it looks like Shell's diminishing-
increment sort ("Shellsort"):

http://www.cs.princeton.edu/~rs/shell/index.html

Two questions:
Q1) Where does the *next* increment get calculated in the upthread source?

Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;
Can someone explain? LS

[Ben Pfaff]

"Lane Straatman" <in*****@invalid.netwrites:

Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Coos Haak]

Op Fri, 12 Jan 2007 13:19:53 -0500 schreef Lane Straatman:

"Eric Sosman" <es*****@acm-dot-org.invalidwrote in message

<snip>

Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;
Can someone explain? LS

K&R2 2.11 Conditional Expressions
--
Coos

[Richard Heathfield]

Ben Pfaff said:

"Lane Straatman" <in*****@invalid.netwrites:

>Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time you see it.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Lane Straatman]

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:a5******************************@bt.com...

Ben Pfaff said:

>"Lane Straatman" <in*****@invalid.netwrites:

>>Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time you see
it.

The parenthesized expressions would have to be logical scalars. LS

[Keith Thompson]

"Lane Straatman" <in*****@invalid.netwrites:
[...]

I'm not so interested in the algorithmic properties but am interested in the
C. Before I read up on it after your post, I thought that they called it a
shell sort because of the way you might move a pea around with a shell as
magicians do. Apparently there's a guy named Shell.

It is an open question on its complexity. It is approximately O(4/3).

[...]

<OT>
O(4/3) doesn't make sense; it's the same as O(1), which is clearly
incorrect. Was that a typo?

According to the Wikipedia article, the original Shell sort is
O(N**2), but a modified version is (hmm, can't do superscripts)
O(N * (log N)**2), which is not as good as the O(N * log N) of
Quicksort and several other algorithms.
</OT>

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Keith Thompson]

"Lane Straatman" <in*****@invalid.invalidwrites:

"Richard Heathfield" <rj*@see.sig.invalidwrote in message
news:a5******************************@bt.com...

>Ben Pfaff said:

>>"Lane Straatman" <in*****@invalid.netwrites:
Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time you see
it.

The parenthesized expressions would have to be logical scalars. LS

What do you mean by "logical scalars"?

The "<" and ">" operators yield a result of type int, with the value
0 or 1. Richard's code above is perfectly valid (apart from the
typo, "int2" for "int_2").

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Lane Straatman]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:
[...]

>I'm not so interested in the algorithmic properties but am interested in
the
C. Before I read up on it after your post, I thought that they called it
a
shell sort because of the way you might move a pea around with a shell as
magicians do. Apparently there's a guy named Shell.

It is an open question on its complexity. It is approximately O(4/3).

[...]

<OT>
O(4/3) doesn't make sense; it's the same as O(1), which is clearly
incorrect. Was that a typo?

I think I pulled a Chomsky and left out an 'n'. The complexity is then
O(n^(4/3)).
What I thought interesting was Dann Corbit's statement that it was this good
"for a judicious choice of [increment]."

According to the Wikipedia article, the original Shell sort is
O(N**2), but a modified version is (hmm, can't do superscripts)
O(N * (log N)**2), which is not as good as the O(N * log N) of
Quicksort and several other algorithms.

You pick your sorts like you pick a poison, but that's algorithms. LS

</OT>

[Lane Straatman]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" writes:

>"Richard Heathfield" wrote in message

>>Ben Pfaff said:
"Lane Straatman" writes:
Q2)I have trouble with the following syntax and seem to be reading
this wrong:
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time you see
it.

The parenthesized expressions would have to be logical scalars. LS

What do you mean by "logical scalars"?

The "<" and ">" operators yield a result of type int, with the value
0 or 1. Richard's code above is perfectly valid (apart from the
typo, "int2" for "int_2").

[x-posted to c.l.f.]
I'm not sure. On the one hand, I could claim that I meant what you wrote,
which is odds-on to be correct, but I wanted to say something that was
metasyntactically correct. We all know that type Boolean is on the other
side of 42nd parallel.

Is there a logical type _Bool defined in the standard? If not, I believe it
would be a common extension in whose details I am interested. LS

[Richard Heathfield]

Keith Thompson said:

Richard's code above is perfectly valid (apart from the
typo, "int2" for "int_2").

<sighOh well. :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Keith Thompson]

"Lane Straatman" <in*****@invalid.netwrites:

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>"Lane Straatman" writes:

>>"Richard Heathfield" wrote in message
Ben Pfaff said:
"Lane Straatman" writes:
>Q2)I have trouble with the following syntax and seem to be reading
>this wrong:
>return int_2 int_1 ? -1 : int_2 != int_1;
>
This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time you see
it.
The parenthesized expressions would have to be logical scalars. LS

What do you mean by "logical scalars"?

The "<" and ">" operators yield a result of type int, with the value
0 or 1. Richard's code above is perfectly valid (apart from the
typo, "int2" for "int_2").

[x-posted to c.l.f.]

Why?? We're talking about C, not Fortran. I've redirected followups
back to comp.lang.c. (Fortran undoubtedly has different rules; if you
want to discuss them, please do so in comp.lang.fortran, not in
comp.lang.c.)

I'm not sure. On the one hand, I could claim that I meant what you wrote,
which is odds-on to be correct, but I wanted to say something that was
metasyntactically correct. We all know that type Boolean is on the other
side of 42nd parallel.

Is there a logical type _Bool defined in the standard? If not, I believe it
would be a common extension in whose details I am interested. LS

C99 introduces a type _Bool, with a typedef "bool" in <stdbool.h>.
But relational operators still yield results of type int, as I wrote
above. See section 9 of the comp.lang.c FAQ, <http://www.c-faq.com/>.

Again, Richard's code, with the typo corrected:

return (int_2 int_1) - (int_2 < int_1);

is perfectly valid C. It might not work in some other language, but
that's hardly relevant here.

I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".

To comp.lang.fortran readers: sorry for the continued intrusion.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

Richard Heathfield wrote:

Ben Pfaff said:

>"Lane Straatman" <in*****@invalid.netwrites:

>>Q2)I have trouble with the following syntax and seem to be
reading this wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

which, admittedly, may take some thinking about, the first time
you see it.

And may actually be more efficient because no instruction cache
need be flushed. All three are immune to arithmetic overflow. The
thinking involves realizing that logical expressions return 0 or 1
only.

--
"I was born lazy. I am no lazier now than I was forty years
ago, but that is because I reached the limit forty years ago.
You can't go beyond possibility." -- Mark Twain

[David T. Ashley]

"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...

"Lane Straatman" <in*****@invalid.netwrites:

>Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.
--
int main(void){char
p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int
putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof
p-1;putchar(p[i]\
);}return 0;}

I'm intrigued by your footer. When I run it, I get a segmentation fault.
I've rearranged it to the form below. What am I doing wrong?

Thanks.

int main(void)
{
char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\n",
*q="kl BIcNBFr.NKEzjwCIxNJC";

int i=sizeof p/2;char *strchr();
int putchar();
while(*q)
{
i+=strchr(p,*q++)-p;
if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]);
}
return 0;
}

[Ben Pfaff]

"David T. Ashley" <dt*@e3ft.comwrites:

I'm intrigued by your footer. When I run it, I get a segmentation fault.
I've rearranged it to the form below. What am I doing wrong?

You dropped the space at the beginning of the second line.
--
"...what folly I commit, I dedicate to you."
--William Shakespeare, _Troilus and Cressida_

[user923005]

Lane Straatman wrote:

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:
[...]

I'm not so interested in the algorithmic properties but am interested in
the
C. Before I read up on it after your post, I thought that they called it
a
shell sort because of the way you might move a pea around with a shell as
magicians do. Apparently there's a guy named Shell.

It is an open question on its complexity. It is approximately O(4/3).

[...]

<OT>
O(4/3) doesn't make sense; it's the same as O(1), which is clearly
incorrect. Was that a typo?

I think I pulled a Chomsky and left out an 'n'. The complexity is then
O(n^(4/3)).
What I thought interesting was Dann Corbit's statement that it was this good
"for a judicious choice of [increment]."

According to the Wikipedia article, the original Shell sort is
O(N**2), but a modified version is (hmm, can't do superscripts)
O(N * (log N)**2), which is not as good as the O(N * log N) of
Quicksort and several other algorithms.

The Wikipedia article is hosed. I don't know who wrote it, but it has
lots of errors.
Here is an accurate analysis of shellsort:
http://citeseer.ist.psu.edu/sedgewick96analysis.html

You pick your sorts like you pick a poison, but that's algorithms. LS

For certain sets, shellsort works marvelously (typically between set
sizes of 100 and 100K items), provided that the data is not reverse
sorted or approximately reverse sorted (which is the worst case input
for insertion sort and the closely related shellsort).

</OT>

[wahaha]

Richard Heathfield wrote:

Ben Pfaff said:

"Lane Straatman" <in*****@invalid.netwrites:

Q2)I have trouble with the following syntax and seem to be reading this
wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

Are we talking about the values as:

If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Then if (int_2 int_1) is true, what ((int_2 int_1) - (int2 <
int_1)) will return? I think the machine shall return 1 (assume trun
== 1 and false == 0), but are we supposed to get a -1 on this issue? Or
maybe I misread somewhere?

>
which, admittedly, may take some thinking about, the first time you see it.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Richard Heathfield]

wahaha said:

>
Richard Heathfield wrote:

>Ben Pfaff said:

"Lane Straatman" <in*****@invalid.netwrites:

Q2)I have trouble with the following syntax and seem to be reading
this wrong
return int_2 int_1 ? -1 : int_2 != int_1;

This is a fairly common idiom.
If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

Yes. Prettier, though, is:

return (int_2 int_1) - (int2 < int_1);

Are we talking about the values as:

If int_2 int_1, it returns -1.
If int_2 == int_1, it returns 0.
If int_2 < int_1, it returns 1.

No.

Then if (int_2 int_1) is true,
what ((int_2 int_1) - (int2 < int_1)) will return?

What is 1 - 0 ?

I think the machine shall return 1 (assume trun
== 1 and false == 0), but are we supposed to get a -1 on this issue? Or
maybe I misread somewhere?

Read more carefully, and consider the following table:

0 - 0 = 0
0 - 1 = -1
1 - 0 = 1

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.

[Giorgio Silvestri]

"Keith Thompson" <ks***@mib.orgha scritto nel messaggio
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:
[...]

I'm not so interested in the algorithmic properties but am interested in

the

C. Before I read up on it after your post, I thought that they called

it a

shell sort because of the way you might move a pea around with a shell

as

magicians do. Apparently there's a guy named Shell.

It is an open question on its complexity. It is approximately O(4/3).

[...]

<OT>
O(4/3) doesn't make sense; it's the same as O(1), which is clearly
incorrect. Was that a typo?

According to the Wikipedia article, the original Shell sort is
O(N**2), but a modified version is (hmm, can't do superscripts)
O(N * (log N)**2), which is not as good as the O(N * log N) of
Quicksort and several other algorithms.

Just a little detail: Quicksort is O(N**2).

--
Giorgio Silvestri
DSP/Embedded/Real Time OS Software Engineer

[Keith Thompson]

"Giorgio Silvestri" <gi**************@libero.itwrites:
[...]

Just a little detail: Quicksort is O(N**2).

I think a naive Quicksort is O(N**2), but I *think* there are tweaks
that can make it O(n log n). (And it's n log n average case, but O()
notation is about worst case.) It's been a while since I studied
this stuff.

(To get back to some semblance of topicality, note that C's qsort()
isn't necessarily Quicksort.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Lane Straatman]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:

>"Keith Thompson" <ks***@mib.orgwrote in message

>>The "<" and ">" operators yield a result of type int, with the value
0 or 1. Richard's code above is perfectly valid (apart from the
typo, "int2" for "int_2").

[x-posted to c.l.f.]

Why?? We're talking about C, not Fortran. I've redirected followups
back to comp.lang.c. (Fortran undoubtedly has different rules; if you
want to discuss them, please do so in comp.lang.fortran, not in
comp.lang.c.)

There's a good chunk of fortran dedicated to interoperability with C.
Critical is that the types match. I thought you were going to say that this
type doesn't exist, which would really do damage to the notion of
interoperability. Indeed, my compiler doesn't even have stdbool.h . The
only reason I was able to dig it up was that it was in the include files of
jacob navia's lcc. Clearly, if one is looking for interoperability, he is
well-advised to have C99 stuff running.

C99 introduces a type _Bool, with a typedef "bool" in <stdbool.h>.
But relational operators still yield results of type int, as I wrote
above. See section 9 of the comp.lang.c FAQ, <http://www.c-faq.com/>.

Again, Richard's code, with the typo corrected:

return (int_2 int_1) - (int_2 < int_1);

is perfectly valid C. It might not work in some other language, but
that's hardly relevant here.

I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".

http://en.wikipedia.org/wiki/Metasyntactic_variable
The 42nd parallel is my vernacular for languages that are intractably at
odds with C, e.g. C++.

/*
WG14/N869 January 18, 1999 Page 257
7.16 Boolean type and values <stdbool.h>
1 The header <stdbool.hdefines four macros.
2 The macro bool expands to _Bool.
3 The remaining three macros are suitable for use in #if preprocessing
directives. They are true which expands to the integer constant 1,
false which expands to the integer constant 0, and _
_bool_true_false_are_defined
which expands to the decimal constant 1.
4 Notwithstanding the provisions of 7.1.3, a program is permitted to
undefine and perhaps
then redefine the macros bool, true, and false
*/
#define bool _Bool
#define true 1
#define false 0
#define __bool_true_false_are_defined 1

Now I'll see if I can make a fortran prog that can come grab this from C.
LS

[Keith Thompson]

"Lane Straatman" <in*****@invalid.netwrites:

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

[...]

>Again, Richard's code, with the typo corrected:

return (int_2 int_1) - (int_2 < int_1);

is perfectly valid C. It might not work in some other language, but
that's hardly relevant here.

I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".

http://en.wikipedia.org/wiki/Metasyntactic_variable

Ok, I know what a metasyntactic variable is (foo, bar, baz, et al). I
still have no idea what you mean by "metasyntactically correct", or
how this might apply to the code in question.

The 42nd parallel is my vernacular for languages that are intractably at
odds with C, e.g. C++.

And I still have no idea what you mean by that.

If you have a point, can you try to make it wihout using obscure
vernacular phrases?

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Eric Sosman]

Lane Straatman wrote:

"Keith Thompson" <ks***@mib.orgwrote in message

>I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".

http://en.wikipedia.org/wiki/Metasyntactic_variable
The 42nd parallel is my vernacular for languages that are intractably at
odds with C, e.g. C++.

If it's yours, then it's not vernacular.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Ian Collins]

Lane Straatman wrote:

The 42nd parallel is my vernacular for languages that are intractably at
odds with C, e.g. C++.

How are they intractably at odds?

--
Ian Collins.

[Lane Straatman]

"Ian Collins" <ia******@hotmail.comwrote in message
news:50*************@mid.individual.net...

Lane Straatman wrote:

>The 42nd parallel is my [idiom] for languages that are intractably at
odds with C, e.g. C++.

How are they intractably at odds?

It's nothing but grief to get them to talk below the OS. The 42nd parallel
was to evoke the 38th: nothing but land mines for would-be crossers. LS

[Ian Collins]

Lane Straatman wrote:

"Ian Collins" <ia******@hotmail.comwrote in message
news:50*************@mid.individual.net...

>>Lane Straatman wrote:

>>>The 42nd parallel is my [idiom] for languages that are intractably at
odds with C, e.g. C++.

How are they intractably at odds?

It's nothing but grief to get them to talk below the OS. The 42nd parallel
was to evoke the 38th: nothing but land mines for would-be crossers. LS

Odd, I've never had any issues and yes, I've written drivers in both.
At least C++ provides an explicit means (extern "C") of linking with C.

--
Ian Collins.

[Lane Straatman]

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

"Lane Straatman" <in*****@invalid.netwrites:

>"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>>I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".

http://en.wikipedia.org/wiki/Metasyntactic_variable

Ok, I know what a metasyntactic variable is (foo, bar, baz, et al). I
still have no idea what you mean by "metasyntactically correct", or
how this might apply to the code in question.

I'm trying to comment on two syntaxes at the same time. In the particular
example (int_a int_b), C yields type int. Fortran is different and I'm
only half-sure on its terminology, hence the cross-post to avail myself of
persons who correct me over there.

I think of most of TAOCP as being metasyntactic. I would be an instant
buyer of _The Essential Knuth in C_ . LS

[Lane Straatman]

"Ian Collins":

Lane Straatman wrote:

>"Ian Collins" <ia******@hotmail.comwrote in message

>>>Lane Straatman wrote:
How are they intractably at odds?

It's nothing but grief to get them to talk below the OS. The 42nd
parallel
was to evoke the 38th: nothing but land mines for would-be crossers. LS

Odd, I've never had any issues and yes, I've written drivers in both.
At least C++ provides an explicit means (extern "C") of linking with C.

This behooves the former, but you can almost feel the flames if you actually
wanted to talk about the subject in candor. LS
------------------
Ian: accidentally sent last response to you

[Keith Thompson]

"Lane Straatman" <in*****@invalid.netwrites:

"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...

>"Lane Straatman" <in*****@invalid.netwrites:

>>"Keith Thompson" <ks***@mib.orgwrote in message
news:ln************@nuthaus.mib.org...
I'm afraid I don't know what you mean by "metasyntactically correct"
or "on the other side of 42nd parallel".
http://en.wikipedia.org/wiki/Metasyntactic_variable

Ok, I know what a metasyntactic variable is (foo, bar, baz, et al). I
still have no idea what you mean by "metasyntactically correct", or
how this might apply to the code in question.

I'm trying to comment on two syntaxes at the same time. In the particular
example (int_a int_b), C yields type int. Fortran is different and I'm
only half-sure on its terminology, hence the cross-post to avail myself of
persons who correct me over there.

I'm sure Fortran is different. It's a different language, with its
own newsgroup. Any discussion of Fortran is off-topic here in
comp.lang.c.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

user923005 wrote:

For certain sets, shellsort works marvelously (typically between set
sizes of 100 and 100K items), provided that the data is not reverse
sorted or approximately reverse sorted (which is the worst case input
for insertion sort and the closely related shellsort).

My observation from timed tests and also from comparison tallying,
is that random order is a much worse case than reversed order,
for Shellsort.

The performance of the N /= 2 increment scheme,
is worst for disordered arrays of (1 << X) number of elements.

Timed tests were done using the e_driver program,
which is in 6 files at:
http://www.mindspring.com/~pfilandr/C/e_driver/

Comparison tallies were done using q_sort.c at:
http://www.mindspring.com/~pfilandr/C/q_sort/q_sort.c

/* BEGIN e_driver.c program output */

Timing 4 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N s2sort s3sort s8sort spsort
0x1fffff 3.234000 2.390000 2.359000 2.187000
0x200000 10.734000 2.375000 2.344000 2.172000
Total times:
s2sort: 13.968000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 4.765000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 4.703000 e_type Shellsort, 3 / 8 increment ratio
spsort: 4.359000 e_type Shellsort, Sedgewick numbers

Distribution #2: Reverse sorted
N s2sort s3sort s8sort spsort
0x1fffff 1.516000 1.141000 1.062000 1.000000
0x200000 1.610000 1.157000 1.094000 1.016000
Total times:
s2sort: 3.126000 e_type Shellsort, 1 / 2 increment ratio
s3sort: 2.298000 e_type Shellsort, 3 / 7 increment ratio
s8sort: 2.156000 e_type Shellsort, 3 / 8 increment ratio
spsort: 2.016000 e_type Shellsort, Sedgewick numbers

/* END e_driver.c program output */
Followup To: comp.programming

--
pete

[pete]

Keith Thompson wrote:

According to the Wikipedia article, the original Shell sort is
O(N**2),

I have observed that behavior, using e_driver.c at:
http://www.mindspring.com/~pfilandr/C/e_driver/

In the following output, s2sort represents the original Shellsort,
and the worst case is Distribution #2: card_shuffle,
with 131072 elements in the test array.

/* BEGIN e_driver.c program output */

Timing 5 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
N s2sort shsort spsort s3sort SI
131071 0.093000 0.078000 0.047000 0.062000 50.937000
131072 0.156000 0.079000 0.047000 0.063000 50.234000
Total times:
s2sort: 0.249000 e_type Shellsort, 1 / 2 increment ratio
shsort: 0.157000 e_type Shellsort, 7 / 16 increment ratio
spsort: 0.094000 e_type Shellsort, Sedgewick numbers
s3sort: 0.125000 e_type Shellsort, 3 / 7 increment ratio
SI: 101.171000 sisort, stable insertion sort

Distribution #2: card_shuffle
N s2sort shsort spsort s3sort SI
131071 0.062000 0.047000 0.031000 0.047000 7.110000
131072 6.828000 0.047000 0.032000 0.047000 7.203000
Total times:
s2sort: 6.890000 e_type Shellsort, 1 / 2 increment ratio
shsort: 0.094000 e_type Shellsort, 7 / 16 increment ratio
spsort: 0.063000 e_type Shellsort, Sedgewick numbers
s3sort: 0.094000 e_type Shellsort, 3 / 7 increment ratio
SI: 14.313000 sisort, stable insertion sort

/* END e_driver.c program output */

--
pete