Class IntroSelector


  • public abstract class IntroSelector
    extends Selector
    Implementation of the quick select algorithm.

    It uses the median of the first, middle and last values as a pivot and falls back to a heap sort when the number of recursion levels exceeds 2 lg(n), as a consequence it runs in linear time on average and in n log(n) time in the worst case.

    NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
    • Constructor Detail

      • IntroSelector

        public IntroSelector()
    • Method Detail

      • select

        public final void select​(int from,
                                 int to,
                                 int k)
        Description copied from class: Selector
        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.
        Specified by:
        select in class Selector
      • compare

        protected int compare​(int i,
                              int j)
        Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).
      • setPivot

        protected abstract void setPivot​(int i)
        Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
      • comparePivot

        protected abstract int comparePivot​(int j)
        Compare the pivot with the slot at j, similarly to compare(i, j).