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.
