On 6/22/14, 10:07 AM, Xinok wrote:
On Sunday, 22 June 2014 at 15:51:13 UTC, Andrei Alexandrescu wrote:
On 6/22/14, 7:47 AM, Xinok wrote:
On Sunday, 22 June 2014 at 08:08:44 UTC, Andrei Alexandrescu wrote:
On 6/21/14, 8:28 AM, Xinok wrote:
That has since been fixed. I implemented heapsort as a fallback
algorithm, effectively making it an introsort.
Wait, when did that happen? I think a better solution would be to take
median of more than 3 elements. -- Andrei
https://github.com/D-Programming-Language/phobos/pull/1735
Thanks. I wonder if it's possible to factor some of the heap sort code
with the BinaryHeap code; they look very similar.
That's a possibility, and BinaryHeap could benefit from it. My heapsort
is over twice as fast and performs almost half the number of comparisons.
Smile, you're on camera! https://issues.dlang.org/show_bug.cgi?id=12966
http://dlang.org/phobos/std_algorithm.html#topN is linear.
Unfortunately not. I managed to trigger quadratic time using the same
test case as above. If you're not aware, topN simply works by
recursively partitioning the range until the Nth element is in place (in
essence, it performs a partial quick sort). The author of this
implementation made the poor decision of simply choosing the last
element as the pivot, not even a median of three.
http://dpaste.dzfl.pl/f30fd2539f66
That would be me, terrible, I know :o). I'd file a task a while ago, now
I assigned you to it if you'd like to take a look:
https://issues.dlang.org/show_bug.cgi?id=12141
Thanks,
Andrei
