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]

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

 

[Lane Straatman]

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]

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.

 

[Coos Haak]

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

"Eric Sosman" <[email protected]> wrote in message

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

 

[Richard Heathfield]

Ben Pfaff said:

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.

 

[Lane Straatman]

Ben Pfaff said:

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

 

[CBFalconer]

Ben Pfaff said:

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.

 

[Keith Thompson]

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 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").

 

[Lane Straatman]

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

 

[Lane Straatman]

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").

<sigh> Oh well.

 

[Keith Thompson]

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.

 

[David T. Ashley]

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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\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\
);}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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\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);
}
return 0;
}

 

[Ben Pfaff]

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.

 

[user923005]

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).

 

[wahaha]

Ben Pfaff said:


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?

 

[Richard Heathfield]

wahaha said:

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

 

[Giorgio Silvestri]

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).