public abstract class IntroSorter extends Sorter
Sorter
implementation based on a variant of the quicksort algorithm
called introsort: when
the recursion level exceeds the log of the length of the array to sort, it
falls back to heapsort. This prevents quicksort from running into its
worst-case quadratic runtime. Small arrays are sorted with
insertion sort.BINARY_SORT_THRESHOLD
Constructor and Description |
---|
IntroSorter()
Create a new
IntroSorter . |
Modifier and Type | Method and 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) void |
quicksort(int from,
int to,
int maxDepth) |
protected abstract void |
setPivot(int i)
Save the value at slot
i so that it can later be used as a
pivot, see Sorter.comparePivot(int) . |
void |
sort(int from,
int to)
Sort the slice which starts at
from (inclusive) and ends at
to (exclusive). |
binarySort, binarySort, checkRange, doRotate, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, siftDown, swap, upper, upper2
public IntroSorter()
IntroSorter
.public final void sort(int from, int to)
Sorter
from
(inclusive) and ends at
to
(exclusive).void quicksort(int from, int to, int maxDepth)
protected abstract void setPivot(int i)
Sorter
i
so that it can later be used as a
pivot, see Sorter.comparePivot(int)
.protected abstract int comparePivot(int j)
Sorter
j
, similarly to
compare(i, j)
.comparePivot
in class Sorter