Fast and memory efficient implementation of a Selection Algorithm in Go.
After calling nth.Element(data sort.Interface, n int)
everything before
index n
will be less than data[n]
and everything after n
will be greater
than or equal to data[n]
. IE it partially sorts data
such that data[n] == sortedData[n]
.
nth.Element
is an implementation of QuickSelectAdaptive
from Andrei
Alexandrescu's 2016 paper
Fast Deterministic Selection. It is has a
deterministic O(n)
runtime, O(1)
space usage. Classical implementations of
Selection Algorithms usually rely on non-determinism (random pivots) or have
high constant factors (median-of-median pivots), or are not as fast as this
algorithm (IntroSelect
).
The name nth.Element
is inspired from C++'s nth_element
, which is also an
implementation of a Selection Algorithm (although most STL implementations use
IntroSelect
).
Note: This is not a complete implementation yet, although already should
be faster than just using sort.Sort
.