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:
|
1 2 3 4 5 6 7 8 9 |
// Declare a random array of values int[] a = { 10, 2, 6, 11, 9, 3, 4, 12, 8, 7, 1, 5 }; // We would like to determine which element // will be at the 6th position of the sorted array: int element = Sort.NthElement(a, 6); // The array will be modified in place to become int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; |
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.