|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object de.lmu.ifi.dbs.elki.math.statistics.QuickSelect
public class QuickSelect
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 |
---|
private static final int SMALL
Constructor Detail |
---|
public QuickSelect()
Method Detail |
---|
public static double quickSelect(double[] data, int rank)
data
- Data to processrank
- Rank position that we are interested in (integer!)
public static double median(double[] data)
data
- Data to process
public static double median(double[] data, int begin, int end)
data
- Data to processbegin
- Begin of valid valuesend
- End of valid values (inclusive!)
public static double quantile(double[] data, double quant)
data
- Data to processquant
- Quantile to compute
public static double quantile(double[] data, int begin, int end, double quant)
data
- Data to processbegin
- Begin of valid valuesend
- End of valid values (inclusive!)quant
- Quantile to compute
public static void quickSelect(double[] data, int start, int end, int rank)
data
- Data to processstart
- Interval startend
- Interval end (inclusive)rank
- rank position we are interested in (starting at 0)private static void insertionSort(double[] data, int start, int end)
data
- Data to sortstart
- Interval startend
- Interval endprivate static final void swap(double[] data, int a, int b)
data
- Arraya
- First indexb
- Second index
|
|
|||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |