Package elki.utilities.datastructures
Class QuickSelect
- java.lang.Object
-
- elki.utilities.datastructures.QuickSelect
-
public class QuickSelect extends java.lang.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.
If you want to use this with a
Comparable
type, use the natural comparatorComparator.naturalOrder()
. You can wrap arrays as lists withjava.util.Arrays#asList
, to sort them in-place, or implement anQuickSelect.Adapter
for your data structure.- Since:
- 0.4.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static interface
QuickSelect.Adapter<T>
Adapter class to apply QuickSelect to arbitrary data structures.
-
Field Summary
Fields Modifier and Type Field 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 Modifier Constructor Description private
QuickSelect()
Do not instantiate - static methods only!
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method 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(double[] data, int start, int end)
Sort a small array using repetitive insertion sort.private static <T> void
insertionSort(java.util.List<T> data, java.util.Comparator<? super T> comparator, 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 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> T
median(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator)
Compute the median of an array efficiently using the QuickSelect method.static <T> T
median(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, 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 <T> T
quantile(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, double quant)
Compute the median of an array efficiently using the QuickSelect method.static <T> T
quantile(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, 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 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(java.util.List<? extends T> data, java.util.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(java.util.List<? extends T> data, java.util.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> 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(java.util.List<T> data, int a, int b)
The usual swap method.
-
-
-
Field Detail
-
SMALL
private static final int SMALL
For small arrays, use a simpler method:- See Also:
- Constant Field Values
-
DOUBLE_ADAPTER
public static final QuickSelect.Adapter<double[]> DOUBLE_ADAPTER
Adapter for double arrays.
-
INTEGER_ADAPTER
public static final QuickSelect.Adapter<int[]> INTEGER_ADAPTER
Adapter for integer arrays.
-
FLOAT_ADAPTER
public static final QuickSelect.Adapter<float[]> FLOAT_ADAPTER
Adapter for float arrays.
-
SHORT_ADAPTER
public static final QuickSelect.Adapter<short[]> SHORT_ADAPTER
Adapter for short arrays.
-
LONG_ADAPTER
public static final QuickSelect.Adapter<long[]> LONG_ADAPTER
Adapter for long arrays.
-
BYTE_ADAPTER
public static final QuickSelect.Adapter<byte[]> BYTE_ADAPTER
Adapter for byte arrays.
-
CHAR_ADAPTER
public static final QuickSelect.Adapter<char[]> CHAR_ADAPTER
Adapter for char arrays.
-
-
Method Detail
-
bestPivot
private static int bestPivot(int rank, int m1, int m2, int m3, int m4, int m5)
Choose the best pivot for the given rank.- Parameters:
rank
- Rankm1
- Pivot candidatem2
- Pivot candidatem3
- Pivot candidatem4
- Pivot candidatem5
- 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 processstart
- Interval startend
- 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 sortstart
- Interval startend
- 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 processrank
- 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 processbegin
- Begin of valid valuesend
- 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 processquant
- 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 processbegin
- Begin of valid valuesend
- 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 processstart
- Interval startend
- 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 sortstart
- Interval startend
- Interval end
-
swap
private static void swap(double[] data, int a, int b)
The usual swap method.- Parameters:
data
- Arraya
- First indexb
- Second index
-
swap
private static <T> void swap(java.util.List<T> data, int a, int b)
The usual swap method.- Type Parameters:
T
- object type- Parameters:
data
- Arraya
- First indexb
- Second index
-
quickSelect
public static <T> T quickSelect(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to userank
- Rank position that we are interested in (integer!)- Returns:
- Value at the given rank
-
median
public static <T> T median(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to use- Returns:
- Median value
-
median
public static <T> T median(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to usebegin
- Begin of valid valuesend
- End of valid values (exclusive!)- Returns:
- Median value
-
quantile
public static <T> T quantile(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to usequant
- Quantile to compute- Returns:
- Value at quantile
-
quantile
public static <T> T quantile(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to usebegin
- Begin of valid valuesend
- End of valid values (inclusive!)quant
- Quantile to compute- Returns:
- Value at quantile
-
quickSelect
public static <T> void quickSelect(java.util.List<? extends T> data, java.util.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 processcomparator
- Comparator to usestart
- Interval startend
- Interval end (inclusive)rank
- rank position we are interested in (starting at 0)
-
insertionSort
private static <T> void insertionSort(java.util.List<T> data, java.util.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 sortstart
- Interval startend
- Interval end
-
-