Selection sort and bubble sort

[user923005]

well, this is likely difficult here (at least if the input structure is not
naturally based around linked lists or similar...). a major potential source
of overhead is likely to be in maintaining and updating the tree structure.

sadly, off hand I don't really know of any tree-sort implementations worth
much consideration for benchmarking (never really been that much into
fine-grained comparative algo benchmarking...).

I have just finished analyzing treesort. It is just heapsort, but
with an explicit (allocated as you go) rather than an implicit heap.
For that reason, it will never perform as well as heapsort. (Though it
will perform identically except with a larger constant of
proportionality due to the memory allocations).

I suggest we could rephrase your suggestion as one for using heapsort,
which is a pretty good decision for all sorts of sorting situations.
Heapsort's best claim to fame is "it never sucks." It may
underperform 'on average' compared to better sorts, but it is simple
to code and never goes quadratic.

 

[cr88192]

The qsort() interface is almost never implemented as quicksort (on
modern compilers).
Once in a while we will find a modified version of Richard Singleton's
ACM algorithm 347.
Much more likely is introspective sort. P. J. Plauger's qsort()
interface is a typical {well done} introspective sort version.

I suppose that there may be a few vendors that have no idea what they
are doing.

I would think that Jon Bentley's article in "Unix Review" of August
1992 would have put a final end to anyone thinking of using ordinary
quicksort as a library function for the qsort() interface.

in my case, a paper from this timeframe is a little before my time...
I was alive then, but not much more can be said (this was before I learned
programming, and I learned programming during my elem school years...).


quicksort usually does pretty well IME.

looking, 'introspective sort':
ok, ok, that is something I have done similar before, just at the time, I
don't think I bailed out and used heapsort, rather I think my failure case
had used selection sort...

as a result, for some inputs it would be slow...

I had used this for a custom BWT implementation, mostly because I had found
that some inputs would blow up the sort function (namely, large blocks with
too much empty space...). in the case of BWT, one can RLE compress the input
and this generally fixes the problem.

[snip]

 

[user923005]

in my case, a paper from this timeframe is a little before my time...
I was alive then, but not much more can be said (this was before I learned
programming, and I learned programming during my elem school years...).

quicksort usually does pretty well IME.

The keyword here is 'usually'. On bad inputs (which are not uncommon
such as already sorted, reverse sorted, organ pipe, and some others)
qsort goes quadratic. In the noted article something that usually ran
in a couple hours ran for a week or two (citing from memory).

The BSD code has some unusually good sorting algorithms in it (both
Radix and qsort() interface).

For some reason, my follow-ups don't seem to be getting set
correctly. I have tried to set follow-ups to comp.programming in
every post I have answered in this thread.