de.lmu.ifi.dbs.elki.math.statistics
Class QuickSelect

java.lang.Object
  extended by de.lmu.ifi.dbs.elki.math.statistics.QuickSelect

public class QuickSelect
extends Object

QuickSelect computes ("selects") the element at a given rank and can be used to compute Medians and arbitrary quantiles by computing the appropriate rank. This algorithm is essentially an incomplete QuickSort that only descends into that part of the data that we are interested in, and also attributed to Charles Antony Richard Hoare


Field Summary
private static int SMALL
          For small arrays, use a simpler method:
 
Constructor Summary
QuickSelect()
           
 
Method Summary
private static void insertionSort(double[] data, int start, int end)
          Sort a small array using repetitive insertion sort.
static double median(double[] data)
          Compute the median of an array efficiently using the QuickSelect method.
static double median(double[] data, int begin, int end)
          Compute the median of an array efficiently using the QuickSelect method.
static double quantile(double[] data, double quant)
          Compute the median of an array efficiently using the QuickSelect method.
static double quantile(double[] data, int begin, int end, double quant)
          Compute the median of an array efficiently using the QuickSelect method.
static double quickSelect(double[] data, int rank)
          QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
static void quickSelect(double[] data, int start, int end, int rank)
          QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
private static void swap(double[] data, int a, int b)
          The usual swap method.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

SMALL

private static final int SMALL
For small arrays, use a simpler method:

See Also:
Constant Field Values
Constructor Detail

QuickSelect

public QuickSelect()
Method Detail

quickSelect

public static double quickSelect(double[] data,
                                 int rank)
QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in. Note: the array is modified by this.

Parameters:
data - Data to process
rank - Rank position that we are interested in (integer!)
Returns:
Value at the given rank

median

public static double median(double[] data)
Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.

Parameters:
data - Data to process
Returns:
Median value

median

public static double median(double[] data,
                            int begin,
                            int end)
Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.

Parameters:
data - Data to process
begin - Begin of valid values
end - End of valid values (inclusive!)
Returns:
Median value

quantile

public static double quantile(double[] data,
                              double quant)
Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.

Parameters:
data - Data to process
quant - Quantile to compute
Returns:
Value at quantile

quantile

public static double quantile(double[] data,
                              int begin,
                              int end,
                              double quant)
Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.

Parameters:
data - Data to process
begin - Begin of valid values
end - End of valid values (inclusive!)
quant - Quantile to compute
Returns:
Value at quantile

quickSelect

public static void quickSelect(double[] data,
                               int start,
                               int end,
                               int rank)
QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.

Parameters:
data - Data to process
start - Interval start
end - Interval end (inclusive)
rank - rank position we are interested in (starting at 0)

insertionSort

private static void insertionSort(double[] data,
                                  int start,
                                  int end)
Sort a small array using repetitive insertion sort.

Parameters:
data - Data to sort
start - Interval start
end - Interval end

swap

private static final void swap(double[] data,
                               int a,
                               int b)
The usual swap method.

Parameters:
data - Array
a - First index
b - Second index

Release 0.4.0 (2011-09-20_1324)