Efficient sorting of pairs<key, value> by value

Question

I'm looking for the most efficient way to sort a bunch of pairs<string, float> by value, because I need to get the 3 highest entries of a high number of pairs.

My natural reaction was to use a sortedList, but apparently it only sorts by key, and I can't use the reversed list solution because I know for a fact that the strings are unique, but the floats might not be.

Any simple and efficient solution I am overlooking?

Answer 1

If you only need to know the top three values, you don't need to sort the whole list - you can just perform one pass, storing the top three values at any one time. That will make it O(n) rather than O(n log n)... but you'll have to implement it yourself.

If you're happy with O(n log n) though, the simplest way would probably be to use LINQ:

var ordered = pairs.OrderBy(pair => pair.Value).Take(3).ToList();

It probably wouldn't be too hard to implement something like:

public static IEnumerable<TSource> TakeTop<TSource, TKey>
    (this IEnumerable<TSource> source,
     Func<TSource, TKey> keySelector,
     int count)

which could have a complexity of O(n * count). If I had a bit more time I'd do it for fun...

Answer 2

You could use linq:

yourDictionary.OrderBy(kv => kv.Value).Take(3);

I don't know about the efficiency, but surely it's short and expressive.