Package 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 Object
A functional forFunUtil.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?
-
-
Field Summary
Fields Modifier and Type Field Description int
TOO_SMALL
-
Constructor Summary
Constructors Constructor Description Quicksorter(T[] vec, Comparator<T> comp)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
partialSort(int limit)
void
select(int limit)
puts the LIMIT biggest items at the head, not sortedvoid
sort()
-
-
-
Field Detail
-
TOO_SMALL
public final int TOO_SMALL
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
Quicksorter
public Quicksorter(T[] vec, Comparator<T> comp)
-
-