Le 13/03/2012 17:38, Xinok a écrit :
On Tuesday, 13 March 2012 at 16:04:55 UTC, deadalnix wrote:
Le 13/03/2012 16:08, Xinok a écrit :
On Tuesday, 13 March 2012 at 09:32:49 UTC, deadalnix wrote:
Le 13/03/2012 10:19, Xinok a écrit :
Would you mind sharing your smoothsort? I haven't implemented one
myself
and I'd love to test it out.
It is on github :
https://github.com/deadalnix/Dsort/blob/master/sort/smooth.d
Thanks. I found a couple cases where it performs better, but overall,
the overhead of the algorithm seems to be too much and most other
algorithms performed better.
smooth sort is intended to be used on semi sorted data (like
transparent polygons on a 3D scene). Ideal to keep some data sorted.
It also have a guarantee to run in O(n*log(n)). But qsort variation
(like we have in phobos) is faster in the general case.
It only performs well if there aren't many elements to move around. For
example, I took a sorted list with 1 million elements, and appended 64
random elements. Smoothsort was the second slowest, only marginally
beating heap sort. My natural merge sort was 27x faster.
Yes, that being said, my implementation use multiple swap where move
would have been more appropriate, and don't implement some improvements.
Merge sort is also known to be very fast (it is default is some
langauges) but trigger memory allocation, something that some cannot afford.
Definitively, this is something we should have in phobos.
