Package org.apache.lucene.util
Class Sorter
- java.lang.Object
-
- org.apache.lucene.util.Sorter
-
- Direct Known Subclasses:
InPlaceMergeSorter
,IntroSorter
,MSBRadixSorter
,TimSorter
public abstract class Sorter extends java.lang.Object
Base class for sorting algorithms implementations.There are a number of subclasses to choose from that vary in performance and stability. We suggest that you pick the first from this ranked list that meets your requirements:
MSBRadixSorter
for strings (array of bytes/chars). Not a stable sort.StableMSBRadixSorter
for strings (array of bytes/chars). Stable sort.IntroSorter
. Not a stable sort.InPlaceMergeSorter
. When the data to sort is typically small. Stable sort.TimSorter
. Stable sort.
-
-
Field Summary
Fields Modifier and Type Field Description (package private) static int
BINARY_SORT_THRESHOLD
(package private) static int
INSERTION_SORT_THRESHOLD
Below this size threshold, the sub-range is sorted using Insertion sort.private int
pivotIndex
-
Constructor Summary
Constructors Modifier Constructor Description protected
Sorter()
Sole constructor, used for inheritance.
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description (package private) void
binarySort(int from, int to)
A binary sort implementation.(package private) void
binarySort(int from, int to, int i)
(package private) void
checkRange(int from, int to)
protected abstract int
compare(int i, int j)
Compare entries found in slotsi
andj
.protected int
comparePivot(int j)
Compare the pivot with the slot atj
, similarly tocompare(i, j)
.(package private) void
doRotate(int lo, int mid, int hi)
(package private) static int
heapChild(int from, int i)
(package private) void
heapify(int from, int to)
(package private) static int
heapParent(int from, int i)
(package private) void
heapSort(int from, int to)
Use heap sort to sort items betweenfrom
inclusive andto
exclusive.(package private) void
insertionSort(int from, int to)
Sorts between from (inclusive) and to (exclusive) with insertion sort.(package private) int
lower(int from, int to, int val)
(package private) int
lower2(int from, int to, int val)
(package private) void
mergeInPlace(int from, int mid, int to)
(package private) void
reverse(int from, int to)
(package private) void
rotate(int lo, int mid, int hi)
protected void
setPivot(int i)
Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.(package private) void
siftDown(int i, int from, int to)
abstract void
sort(int from, int to)
Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).protected abstract void
swap(int i, int j)
Swap values at slotsi
andj
.(package private) int
upper(int from, int to, int val)
(package private) int
upper2(int from, int to, int val)
-
-
-
Field Detail
-
BINARY_SORT_THRESHOLD
static final int BINARY_SORT_THRESHOLD
- See Also:
- Constant Field Values
-
INSERTION_SORT_THRESHOLD
static final int INSERTION_SORT_THRESHOLD
Below this size threshold, the sub-range is sorted using Insertion sort.- See Also:
- Constant Field Values
-
pivotIndex
private int pivotIndex
-
-
Method Detail
-
compare
protected abstract 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)
.
-
swap
protected abstract void swap(int i, int j)
Swap values at slotsi
andj
.
-
setPivot
protected void setPivot(int i)
Save the value at sloti
so that it can later be used as a pivot, seecomparePivot(int)
.
-
comparePivot
protected int comparePivot(int j)
Compare the pivot with the slot atj
, similarly tocompare(i, j)
.
-
sort
public abstract void sort(int from, int to)
Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).
-
checkRange
void checkRange(int from, int to)
-
mergeInPlace
void mergeInPlace(int from, int mid, int to)
-
lower
int lower(int from, int to, int val)
-
upper
int upper(int from, int to, int val)
-
lower2
int lower2(int from, int to, int val)
-
upper2
int upper2(int from, int to, int val)
-
reverse
final void reverse(int from, int to)
-
rotate
final void rotate(int lo, int mid, int hi)
-
doRotate
void doRotate(int lo, int mid, int hi)
-
binarySort
void binarySort(int from, int to)
A binary sort implementation. This performsO(n*log(n))
comparisons andO(n^2)
swaps. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort has become less than 20. This algorithm is stable.
-
binarySort
void binarySort(int from, int to, int i)
-
insertionSort
void insertionSort(int from, int to)
Sorts between from (inclusive) and to (exclusive) with insertion sort. Runs inO(n^2)
. It is typically used by more sophisticated implementations as a fall-back when the number of items to sort becomes less than 16. This algorithm is stable.
-
heapSort
void heapSort(int from, int to)
Use heap sort to sort items betweenfrom
inclusive andto
exclusive. This runs inO(n*log(n))
and is used as a fall-back byIntroSorter
. This algorithm is NOT stable.
-
heapify
void heapify(int from, int to)
-
siftDown
void siftDown(int i, int from, int to)
-
heapParent
static int heapParent(int from, int i)
-
heapChild
static int heapChild(int from, int i)
-
-