Package org.apache.lucene.util

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 median of medians when the number of recursion levels exceeds 2 lg(n), as a consequence it runs in linear time on average.

    • Constructor Summary

      Constructors 
      Constructor Description
      IntroSelector()  

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected int compare​(int i, int j)
      Compare entries found in slots i and j.
      protected abstract int comparePivot​(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).
      (package private) int medianOfMediansSelect​(int left, int right, int k)  
      private int partition​(int left, int right, int k, int pivotIndex)  
      private int partition5​(int left, int right)  
      private int pivot​(int left, int right)  
      private void quickSelect​(int from, int to, int k, int maxDepth)  
      void select​(int from, int to, int k)
      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.
      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).
      (package private) int slowSelect​(int from, int to, int k)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • 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

      • slowSelect

        int slowSelect​(int from,
               int to,
               int k)

      • medianOfMediansSelect

        int medianOfMediansSelect​(int left,
                          int right,
                          int k)

      • partition

        private int partition​(int left,
                      int right,
                      int k,
                      int pivotIndex)

      • pivot

        private int pivot​(int left,
                  int right)

      • partition5

        private int partition5​(int left,
                       int right)

      • quickSelect

        private void quickSelect​(int from,
                         int to,
                         int k,
                         int maxDepth)

      • 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).