C# equivalent to std::nth_element

Let’s say you would like to determine what is the second largest element in an array, but you don’t want to pay the cost of sorting the entire array just to discover which value would fall into this position.

In those situations, you would use std::nth_element to partially sort the array such that the element that you want will fall in the n-th position that you need.

The std::nth_element function also goes one step further: it guarantees that all elements on the left of the nth position that you asked for will be less than the value in that position. Those values, however, can be in arbitrary order.

Unfortunately, knowing the niftiness of this function doesn’t help much if you can’t call it from the environment you are programming in. The good news is that, if you are in .NET, you can call Accord.Sort.NthElement (overloads) from C#, VB.NET or any other .NET language using Accord.NET.

An example can be seen below:

The careful reader might have noticed that the entire array has been sorted, instead of just the left part as previously advertised. However, this is on purpose: for very small arrays (like the one in this example), it is more advantageous to use a full, but simpler, sorting algorithm than partial quicksort. When the arrays are large enough (the current threshold is 32 elements), a partial quicksort with a median-of-three pivoting strategy kicks in.

The source code for the function can be found here.

Leave a Reply

Your email address will not be published. Required fields are marked *