mondrian.olap.fun
Class FunUtil.Quicksorter<T>

java.lang.Object
  extended by 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?


Field Summary
 int TOO_SMALL
           
 
Constructor Summary
FunUtil.Quicksorter(T[] vec, java.util.Comparator<T> comp)
           
 
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
 

Field Detail

TOO_SMALL

public final int TOO_SMALL
See Also:
Constant Field Values
Constructor Detail

FunUtil.Quicksorter

public FunUtil.Quicksorter(T[] vec,
                           java.util.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)

Get Mondrian at SourceForge.net. Fast, secure and free Open Source software downloads