core/org.gnit.lucenekmp.util/IntroSelector

IntroSelector

Adaptive selection algorithm based on the introspective quick select algorithm. The quick select algorithm uses an interpolation variant of Tukey's ninther median-of-medians for pivot, and Bentley-McIlroy 3-way partitioning. For the introspective protection, it shuffles the sub-range if the max recursive depth is exceeded.

This selection algorithm is fast on most data shapes, especially on nearly sorted data, or when k is close to the boundaries. It runs in linear time on average.

Constructors

IntroSelector

constructor()

Functions

checkArgs

fun checkArgs(from: Int, to: Int, k: Int)

select

open override fun select(from: Int, to: Int, k: Int)

Reorder elements so that the element at position k is the same as if all elements were sorted and all other elements are partitioned around it: [from, k) only contains elements that are less than or equal to k and (k, to) only contains elements that are greater than or equal to k.

fun select(from: Int, to: Int, k: Int, maxDepth: Int)