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
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected int
compare(int i, int j)
Compare entries found in slotsi
andj
.protected abstract int
comparePivot(int j)
Compare the pivot with the slot atj
, similarly tocompare(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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
.protected abstract void
setPivot(int i)
Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.(package private) int
slowSelect(int from, int to, int k)
-
-
-
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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
.
-
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 slotsi
andj
. The contract for the returned value is the same asComparator.compare(Object, Object)
.
-
setPivot
protected abstract void setPivot(int i)
Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.
-
comparePivot
protected abstract int comparePivot(int j)
Compare the pivot with the slot atj
, similarly tocompare(i, j)
.
-
-