Package org.apache.lucene.util

Class IntroSelector

java.lang.Object
org.apache.lucene.util.Selector
org.apache.lucene.util.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

    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)
     
    final 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 org.apache.lucene.util.Selector

    checkArgs, swap

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • IntroSelector

      public IntroSelector()

  • Method Details

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