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

Author:

Erich Schubert

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static interface QuickSelect.Adapter<T>
Adapter class to apply QuickSelect to arbitrary data structures.

Nested Classes
Modifier and Type	Class and Description
`static interface`	`QuickSelect.Adapter<T>` Adapter class to apply QuickSelect to arbitrary data structures.

Field Summary

Fields
Modifier and Type	Field and Description
`static QuickSelect.Adapter<byte[]>`	`BYTE_ADAPTER` Adapter for byte arrays.
`static QuickSelect.Adapter<char[]>`	`CHAR_ADAPTER` Adapter for char arrays.
`static QuickSelect.Adapter<double[]>`	`DOUBLE_ADAPTER` Adapter for double arrays.
`static QuickSelect.Adapter<float[]>`	`FLOAT_ADAPTER` Adapter for float arrays.
`static QuickSelect.Adapter<int[]>`	`INTEGER_ADAPTER` Adapter for integer arrays.
`static QuickSelect.Adapter<long[]>`	`LONG_ADAPTER` Adapter for long arrays.
`static QuickSelect.Adapter<short[]>`	`SHORT_ADAPTER` Adapter for short arrays.
`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 int`	`bestPivot(int rank, int m1, int m2, int m3, int m4, int m5)` Choose the best pivot for the given rank.
`private static void`	`insertionSort(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, int start, int end, DBIDArrayIter iter1, DBIDArrayIter iter2)` 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 void`	`insertionSort(ModifiableDoubleDBIDList data, int start, int end, DoubleDBIDListIter iter1, DoubleDBIDListIter iter2)` 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.
`private static <T> void`	`insertionSort(T data, QuickSelect.Adapter<T> adapter, int start, int end)` Sort a small array using repetitive insertion sort.
`static int`	`median(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator)` Compute the median of an array efficiently using the QuickSelect method.
`static int`	`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 int`	`median(ModifiableDoubleDBIDList data)` Compute the median of an array efficiently using the QuickSelect method.
`static int`	`median(ModifiableDoubleDBIDList 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 int`	`quantile(ArrayModifiableDBIDs data, Comparator<? super DBIDRef> comparator, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static int`	`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 int`	`quantile(ModifiableDoubleDBIDList data, double quant)` Compute the median of an array efficiently using the QuickSelect method.
`static int`	`quantile(ModifiableDoubleDBIDList 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 void`	`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 double`	`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 void`	`quickSelect(ModifiableDoubleDBIDList 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(ModifiableDoubleDBIDList 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.
`static <T> void`	`quickSelect(T data, QuickSelect.Adapter<T> adapter, 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
  - DOUBLE_ADAPTER
```
public static QuickSelect.Adapter<double[]> DOUBLE_ADAPTER
```
    Adapter for double arrays.
  - INTEGER_ADAPTER
```
public static QuickSelect.Adapter<int[]> INTEGER_ADAPTER
```
    Adapter for integer arrays.
  - FLOAT_ADAPTER
```
public static QuickSelect.Adapter<float[]> FLOAT_ADAPTER
```
    Adapter for float arrays.
  - SHORT_ADAPTER
```
public static QuickSelect.Adapter<short[]> SHORT_ADAPTER
```
    Adapter for short arrays.
  - LONG_ADAPTER
```
public static QuickSelect.Adapter<long[]> LONG_ADAPTER
```
    Adapter for long arrays.
  - BYTE_ADAPTER
```
public static QuickSelect.Adapter<byte[]> BYTE_ADAPTER
```
    Adapter for byte arrays.
  - CHAR_ADAPTER
```
public static QuickSelect.Adapter<char[]> CHAR_ADAPTER
```
    Adapter for char arrays.
- Constructor Detail
  - QuickSelect
```
public QuickSelect()
```
- Method Detail
  - bestPivot
```
private static final int bestPivot(int rank,
            int m1,
            int m2,
            int m3,
            int m4,
            int m5)
```
    Choose the best pivot for the given rank.
    
    Parameters:
    rank - Rank
    m1 - Pivot candidate
    m2 - Pivot candidate
    m3 - Pivot candidate
    m4 - Pivot candidate
    m5 - Pivot candidate
    
    Returns:
    Best pivot candidate
  - quickSelect
```
public static <T> void quickSelect(T data,
                   QuickSelect.Adapter<T> adapter,
                   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 <T> void insertionSort(T data,
                     QuickSelect.Adapter<T> adapter,
                     int start,
                     int end)
```
    Sort a small array using repetitive insertion sort.
    
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end
  - 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 double 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)
    
    Returns:
    Element at the given rank (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 void 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!)
  - median
```
public static int 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 position
  - median
```
public static int 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 position
  - quantile
```
public static int 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:
    Quantile position
  - quantile
```
public static int 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 (exclusive)
    quant - Quantile to compute
    
    Returns:
    Quantile position
  - 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 (exclusive)
    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,
                 DBIDArrayIter iter1,
                 DBIDArrayIter iter2)
```
    Sort a small array using repetitive insertion sort.
    
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end
  - quickSelect
```
public static void quickSelect(ModifiableDoubleDBIDList 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!)
  - median
```
public static int median(ModifiableDoubleDBIDList 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 position
  - median
```
public static int median(ModifiableDoubleDBIDList 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.
    
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive!)
    
    Returns:
    Median position
  - quantile
```
public static int quantile(ModifiableDoubleDBIDList 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:
    Quantile position
  - quantile
```
public static int quantile(ModifiableDoubleDBIDList 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.
    
    Parameters:
    data - Data to process
    begin - Begin of valid values
    end - End of valid values (exclusive)
    quant - Quantile to compute
    
    Returns:
    Quantile position
  - quickSelect
```
public static void quickSelect(ModifiableDoubleDBIDList 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(ModifiableDoubleDBIDList data,
                 int start,
                 int end,
                 DoubleDBIDListIter iter1,
                 DoubleDBIDListIter iter2)
```
    Sort a small array using repetitive insertion sort.
    
    Parameters:
    data - Data to sort
    start - Interval start
    end - Interval end

Class QuickSelect

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

SMALL

DOUBLE_ADAPTER

INTEGER_ADAPTER

FLOAT_ADAPTER

SHORT_ADAPTER

LONG_ADAPTER

BYTE_ADAPTER

CHAR_ADAPTER

Constructor Detail

QuickSelect

Method Detail

bestPivot

quickSelect

insertionSort

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

quickSelect

median

median

quantile

quantile

quickSelect

insertionSort