QuickSelect (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.utilities.datastructures.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

Fields
Modifier and Type Field and Description

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

Fields
Modifier and Type	Field and Description
`private static int`	`SMALL` For small arrays, use a simpler method:

Constructor Summary

Constructors
Constructor and Description

QuickSelect()

Constructors
Constructor and Description
`QuickSelect()`

Method Summary

Methods
Modifier and Type	Method and Description
`private static void`	`insertionSort(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, int start, int end)` Sort a small array using repetitive insertion sort.
`private static void`	`insertionSort(double[] data, int start, int end)` Sort a small array using repetitive insertion sort.
`private static <T> void`	`insertionSort(List<T> data, Comparator<? super T> comparator, int start, int end)` Sort a small array using repetitive insertion sort.
`private static <T extends Comparable<? super T>> void`	`insertionSort(List<T> data, int start, int end)` Sort a small array using repetitive insertion sort.
`private static <T extends Comparable<? super T>> void`	`insertionSort(T[] data, int start, int end)` Sort a small array using repetitive insertion sort.
`static DBID`	`median(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator)` Compute the median of an array efficiently using the QuickSelect method.
`static DBID`	`median(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, int begin, int end)` Compute the median of an array efficiently using the QuickSelect method.
`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 <T extends Comparable<? super T>> T`	`median(List<? extends T> data)` Compute the median of an array efficiently using the QuickSelect method.
`static <T> T`	`median(List<? extends T> data, Comparator<? super T> comparator)` Compute the median of an array efficiently using the QuickSelect method.
`static <T> T`	`median(List<? extends T> data, Comparator<? super T> comparator, int begin, int end)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`median(List<? extends T> data, int begin, int end)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`median(T[] data)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`median(T[] data, int begin, int end)` Compute the median of an array efficiently using the QuickSelect method.
`static DBID`	`quantile(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static DBID`	`quantile(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, int begin, int end, double quant)` 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 <T> T`	`quantile(List<? extends T> data, Comparator<? super T> comparator, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static <T> T`	`quantile(List<? extends T> data, Comparator<? super T> comparator, int begin, int end, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`quantile(List<? extends T> data, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`quantile(List<? extends T> data, int begin, int end, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`quantile(T[] data, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static <T extends Comparable<? super T>> T`	`quantile(T[] data, int begin, int end, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static DBID`	`quickSelect(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, int rank)` QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
`static void`	`quickSelect(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, 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.
`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.
`static <T> T`	`quickSelect(List<? extends T> data, Comparator<? super T> comparator, int rank)` QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
`static <T> void`	`quickSelect(List<? extends T> data, Comparator<? super T> comparator, 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.
`static <T extends Comparable<? super T>> T`	`quickSelect(List<? extends T> data, int rank)` QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
`static <T extends Comparable<? super T>> void`	`quickSelect(List<? extends T> 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.
`static <T extends Comparable<? super T>> T`	`quickSelect(T[] data, int rank)` QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
`static <T extends Comparable<? super T>> void`	`quickSelect(T[] 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.
`private static <T> void`	`swap(List<T> data, int a, int b)` The usual swap method.
`private static <T extends Comparable<? super T>> void`	`swap(T[] 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 (exclusive!)
    
    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 (exclusive!)
    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 (exclusive)
    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
  - quickSelect
```
public static <T extends Comparable<? super T>> T quickSelect(T[] 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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    rank - Rank position that we are interested in (integer!)
    
    Returns:
    Value at the given rank
  - median
```
public static <T extends Comparable<? super T>> T median(T[] 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 <T extends Comparable<? super T>> T median(T[] data,
                                         int begin,
                                         int end)
```
    Compute the median of an array efficiently using the QuickSelect method. On an odd length, it will return the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    
    Returns:
    Median value
  - quantile
```
public static <T extends Comparable<? super T>> T quantile(T[] data,
                                           double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quantile
```
public static <T extends Comparable<? super T>> T quantile(T[] data,
                                           int begin,
                                           int end,
                                           double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. It will prefer the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quickSelect
```
public static <T extends Comparable<? super T>> void quickSelect(T[] 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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    start - Interval start
    end - Interval end (exclusive)
    rank - rank position we are interested in (starting at 0)
  - insertionSort
```
private static <T extends Comparable<? super T>> void insertionSort(T[] data,
                                                   int start,
                                                   int end)
```
    Sort a small array using repetitive insertion sort.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end
  - swap
```
private static final <T extends Comparable<? super T>> void swap(T[] data,
                                          int a,
                                          int b)
```
    The usual swap method.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Array
    a - First index
    b - Second index
  - quickSelect
```
public static <T extends Comparable<? super T>> T quickSelect(List<? extends T> 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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    rank - Rank position that we are interested in (integer!)
    
    Returns:
    Value at the given rank
  - median
```
public static <T extends Comparable<? super T>> T median(List<? extends T> data)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    
    Returns:
    Median value
  - median
```
public static <T extends Comparable<? super T>> T median(List<? extends T> data,
                                         int begin,
                                         int end)
```
    Compute the median of an array efficiently using the QuickSelect method. On an odd length, it will return the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    
    Returns:
    Median value
  - quantile
```
public static <T extends Comparable<? super T>> T quantile(List<? extends T> data,
                                           double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quantile
```
public static <T extends Comparable<? super T>> T quantile(List<? extends T> data,
                                           int begin,
                                           int end,
                                           double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. It will prefer the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quickSelect
```
public static <T extends Comparable<? super T>> void quickSelect(List<? extends T> 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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    start - Interval start
    end - Interval end (exclusive)
    rank - rank position we are interested in (starting at 0)
  - insertionSort
```
private static <T extends Comparable<? super T>> void insertionSort(List<T> data,
                                                   int start,
                                                   int end)
```
    Sort a small array using repetitive insertion sort.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end
  - swap
```
private static final <T> void swap(List<T> data,
            int a,
            int b)
```
    The usual swap method.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Array
    a - First index
    b - Second index
  - quickSelect
```
public static <T> T quickSelect(List<? extends T> data,
                Comparator<? super T> comparator,
                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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    rank - Rank position that we are interested in (integer!)
    
    Returns:
    Value at the given rank
  - median
```
public static <T> T median(List<? extends T> data,
           Comparator<? super T> comparator)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    
    Returns:
    Median value
  - median
```
public static <T> T median(List<? extends T> data,
           Comparator<? super T> comparator,
           int begin,
           int end)
```
    Compute the median of an array efficiently using the QuickSelect method. On an odd length, it will return the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    
    Returns:
    Median value
  - quantile
```
public static <T> T quantile(List<? extends T> data,
             Comparator<? super T> comparator,
             double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quantile
```
public static <T> T quantile(List<? extends T> data,
             Comparator<? super T> comparator,
             int begin,
             int end,
             double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. It will prefer the lower element. Note: the array is modified by this.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    begin - Begin of valid values
    end - End of valid values (inclusive!)
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quickSelect
```
public static <T> void quickSelect(List<? extends T> data,
                   Comparator<? super T> comparator,
                   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.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to process
    comparator - Comparator to use
    start - Interval start
    end - Interval end (inclusive)
    rank - rank position we are interested in (starting at 0)
  - insertionSort
```
private static <T> void insertionSort(List<T> data,
                     Comparator<? super T> comparator,
                     int start,
                     int end)
```
    Sort a small array using repetitive insertion sort.
    
    Type Parameters:
    T - object type
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end
  - quickSelect
```
public static DBID quickSelect(ArrayModifiableDBIDs data,
               Comparator<? super DBIDRef> comparator,
               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
    comparator - Comparator to use
    rank - Rank position that we are interested in (integer!)
    
    Returns:
    Value at the given rank
  - median
```
public static DBID median(ArrayModifiableDBIDs data,
          Comparator<? super DBIDRef> comparator)
```
    Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
    
    Parameters:
    data - Data to process
    comparator - Comparator to use
    
    Returns:
    Median value
  - median
```
public static DBID median(ArrayModifiableDBIDs data,
          Comparator<? super DBIDRef> comparator,
          int begin,
          int end)
```
    Compute the median of an array efficiently using the QuickSelect method. On an odd length, it will return the lower element. Note: the array is modified by this.
    
    Parameters:
    data - Data to process
    comparator - Comparator to use
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    
    Returns:
    Median value
  - quantile
```
public static DBID quantile(ArrayModifiableDBIDs data,
            Comparator<? super DBIDRef> comparator,
            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
    comparator - Comparator to use
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quantile
```
public static DBID quantile(ArrayModifiableDBIDs data,
            Comparator<? super DBIDRef> comparator,
            int begin,
            int end,
            double quant)
```
    Compute the median of an array efficiently using the QuickSelect method. It will prefer the lower element. Note: the array is modified by this.
    
    Parameters:
    data - Data to process
    comparator - Comparator to use
    begin - Begin of valid values
    end - End of valid values (inclusive!)
    quant - Quantile to compute
    
    Returns:
    Value at quantile
  - quickSelect
```
public static void quickSelect(ArrayModifiableDBIDs data,
               Comparator<? super DBIDRef> comparator,
               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
    comparator - Comparator to use
    start - Interval start
    end - Interval end (inclusive)
    rank - rank position we are interested in (starting at 0)
  - insertionSort
```
private static void insertionSort(ArrayModifiableDBIDs data,
                 Comparator<? super DBIDRef> comparator,
                 int start,
                 int end)
```
    Sort a small array using repetitive insertion sort.
    
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end

Class QuickSelect

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

SMALL

Constructor Detail

QuickSelect

Method Detail

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort

swap

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort

swap

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort

swap

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort