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

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