de.lmu.ifi.dbs.elki.utilities.datastructures

Class QuickSelect

java.lang.Object

de.lmu.ifi.dbs.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 comparator Comparator.naturalOrder(). You can wrap arrays as lists with java.util.Arrays#asList, to sort them in-place, or implement an QuickSelect.Adapter for your data structure.

Since:

0.4.0

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.

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

Modifier	Constructor and Description
private	QuickSelect() Do not instantiate - static methods only!

Method Summary

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(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.

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

private QuickSelect()

Do not instantiate - static methods only!

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

swap

private static final <T> void swap(java.util.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(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 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(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 process

comparator - 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 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(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 process

comparator - Comparator to use

quant - 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 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(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 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(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 sort

start - Interval start

end - Interval end