mondrian.olap.fun
Class FunUtil.Quicksorter<T>
java.lang.Object
mondrian.olap.fun.FunUtil.Quicksorter<T>
- Enclosing class:
- FunUtil
static class FunUtil.Quicksorter<T>
- extends java.lang.Object
A functional for FunUtil.partialSort(java.lang.Object[], java.util.Comparator, 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?
Method Summary |
void |
partialSort(int limit)
|
void |
select(int limit)
puts the LIMIT biggest items at the head, not sorted |
void |
sort()
|
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
TOO_SMALL
public final int TOO_SMALL
- See Also:
- Constant Field Values
FunUtil.Quicksorter
public FunUtil.Quicksorter(T[] vec,
java.util.Comparator<T> comp)
sort
public void sort()
select
public void select(int limit)
- puts the LIMIT biggest items at the head, not sorted
partialSort
public void partialSort(int limit)