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 for 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?

Field Summary

Fields

Modifier and Type	Field and Description
int	TOO_SMALL

Constructor Summary

Constructors

Constructor and Description
Quicksorter(T[] vec, Comparator<T> comp)

Method Summary

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()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

TOO_SMALL

public final int TOO_SMALL

See Also:

Constant Field Values

Constructor Detail

Quicksorter

public Quicksorter(T[] vec,
                   Comparator<T> comp)

Method Detail

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)