On Tuesday, 24 June 2014 at 11:50:37 UTC, Xinok wrote:
On Tuesday, 24 June 2014 at 04:40:48 UTC, Peter Alexander wrote:
On Monday, 23 June 2014 at 22:47:20 UTC, Xinok wrote:
What do you all think? Do you agree with my definition of
stable topN? Do you know of a better algorithm/approach for
implementing this function?
I agree with your definition, and can't think of a better
algorithm, but wouldn't a stable sort have the same effect as
your algorithm? Both are O(n lg(n)) time and O(n) space.
A stable sort would lose the original ordering of the elements
though. Furthermore, the entire point of the topN function is
to be faster than simply sorting the range.
Yeah ignore me. Just woke up realising I'd made that mistake, but
you've already replied :-)
However, is your version faster? The last stable partition step
is O(n lg n), same as stable sort.
