static class FunUtil.Quicksorter<T> extends Object
FunUtil.partialSort(T[], java.util.Comparator<T>, int)
.
Sorts or partially sorts an array in ascending order, using a Comparator.
Algorithm: quicksort, or partial quicksort (alias "quickselect"), Hoare/Singleton. Partial quicksort is quicksort that recurs only on one side, which is thus tail-recursion. Picks pivot as median of three; falls back on insertion sort for small "subfiles". Partial quicksort is O(n + m log m), instead of O(n log n), where n is the input size, and m is the desired output size.
See D Knuth, Art of Computer Programming, 5.2.2 (Algorithm Q); R. Sedgewick, Algorithms in C, ch 5. Good summary in http://en.wikipedia.org/wiki/Selection_algorithm
TODO: What is the time-cost of this functor and of the nested Comparators?
Modifier and Type | Field and Description |
---|---|
int |
TOO_SMALL |
Constructor and Description |
---|
FunUtil.Quicksorter(T[] vec,
Comparator<T> comp) |
Modifier and Type | Method and Description |
---|---|
void |
partialSort(int limit) |
void |
select(int limit)
puts the LIMIT biggest items at the head, not sorted
|
void |
sort() |
public final int TOO_SMALL
public FunUtil.Quicksorter(T[] vec, Comparator<T> comp)
public void sort()
public void select(int limit)
public void partialSort(int limit)