Re: A question about sort stable
On Mar 30, 7:07 pm, Joe Wright <joewwri...@com cast.netwrote:
Weak heapsort is faster (but requires N additional bits of storage,
and therefore is not totally 'in place')
Related, very intersting paper:
"Implementi ng HEAPSORT with n log n -0.9n and QUICKSORT with n log n +
0.2n Comparisons"
Stefan Edelkamp, Patrick Stiegeler
You can find the source code for this project here:
For integers, you can sort in n* log(log(n))
These look interesting:
"A Heap-Based Optimal Inversions-Sensitive Sorting Algorithm"
Srinath Sridhar
The papers on generalized quicksort and on presorting also look very
interesting.
Of course, for multiple CPU/multiple disk systems, everything changes
and some other algorithms dominate.
On Mar 30, 7:07 pm, Joe Wright <joewwri...@com cast.netwrote:
Keith Thompson wrote:
>
>
>
Please nominate an in place array sort for qsort() quicker than the
quicksort. I like insertion sorts and especially Shell sorts because
they are simpler. But they are not quicker.
"Malcolm McLean" <regniz...@btin ternet.comwrite s:
[...]
"Richard Harter" <c...@tiac.netw rote in message
>Your description applies to quicksort; IIANM qsort is a library routine
>that can be implemented in any old way that the implementor feels like
>using, including a stable sort.
>that can be implemented in any old way that the implementor feels like
>using, including a stable sort.
Strictly you are right. However if a function called qsort() doesn't
implement quicksort then you ought to send it back.
implement quicksort then you ought to send it back.
Why? There are plenty of good sorting algorithms other than
Quicksort. Why shouldn't qsort() use one of them?
Quicksort. Why shouldn't qsort() use one of them?
Please nominate an in place array sort for qsort() quicker than the
quicksort. I like insertion sorts and especially Shell sorts because
they are simpler. But they are not quicker.
and therefore is not totally 'in place')
Related, very intersting paper:
"Implementi ng HEAPSORT with n log n -0.9n and QUICKSORT with n log n +
0.2n Comparisons"
Stefan Edelkamp, Patrick Stiegeler
You can find the source code for this project here:
For integers, you can sort in n* log(log(n))
These look interesting:
"A Heap-Based Optimal Inversions-Sensitive Sorting Algorithm"
Srinath Sridhar
The papers on generalized quicksort and on presorting also look very
interesting.
Of course, for multiple CPU/multiple disk systems, everything changes
and some other algorithms dominate.
Comment