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

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

`public class QuickSelectextends 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:

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)