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.
Yes you can't use stable sort. However you can use a priority
queue, which would made the algorithm worst case O(M log N) in
time and O(N) in space. (M is the number of elements in the
original array and N the number of top elements)
