what type of sort is this?

[Keith Thompson]

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

 

[Lane Straatman]

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.h> defines 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]

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?

 

[Eric Sosman]

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.

 

[Ian Collins]

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

How are they intractably at odds?

 

[Lane Straatman]

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]

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.

 

[Lane Straatman]

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":

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

 

[Keith Thompson]

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.

 

[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]

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 */