public abstract class Sorter
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
(package private) static int |
BINARY_SORT_THRESHOLD |
private int |
pivotIndex |
Modifier | Constructor and Description |
---|---|
protected |
Sorter()
Sole constructor, used for inheritance.
|
Modifier and Type | Method and 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 slots
i and j . |
protected int |
comparePivot(int j)
Compare the pivot with the slot at
j , similarly to
compare(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 between
from inclusive and to
exclusive. |
(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 slot
i so that it can later be used as a
pivot, see comparePivot(int) . |
(package private) void |
siftDown(int i,
int from,
int to) |
abstract void |
sort(int from,
int to)
Sort the slice which starts at
from (inclusive) and ends at
to (exclusive). |
protected abstract void |
swap(int i,
int j)
Swap values at slots
i and j . |
(package private) int |
upper(int from,
int to,
int val) |
(package private) int |
upper2(int from,
int to,
int val) |
static final int BINARY_SORT_THRESHOLD
private int pivotIndex
protected abstract int compare(int i, int j)
i
and j
.
The contract for the returned value is the same as
Comparator.compare(Object, Object)
.protected abstract void swap(int i, int j)
i
and j
.protected void setPivot(int i)
i
so that it can later be used as a
pivot, see comparePivot(int)
.protected int comparePivot(int j)
j
, similarly to
compare(i, j)
.public abstract void sort(int from, int to)
from
(inclusive) and ends at
to
(exclusive).void checkRange(int from, int to)
void mergeInPlace(int from, int mid, int to)
int lower(int from, int to, int val)
int upper(int from, int to, int val)
int lower2(int from, int to, int val)
int upper2(int from, int to, int val)
final void reverse(int from, int to)
final void rotate(int lo, int mid, int hi)
void doRotate(int lo, int mid, int hi)
void binarySort(int from, int to)
O(n*log(n))
comparisons
and O(n^2)
swaps. It is typically used by more sophisticated
implementations as a fall-back when the numbers of items to sort has become
less than 20.void binarySort(int from, int to, int i)
void heapSort(int from, int to)
from
inclusive and to
exclusive. This runs in O(n*log(n))
and is used as a fall-back by
IntroSorter
.void heapify(int from, int to)
void siftDown(int i, int from, int to)
static int heapParent(int from, int i)
static int heapChild(int from, int i)