Package elki.database.ids
Class QuickSelectDBIDs
- java.lang.Object
-
- elki.database.ids.QuickSelectDBIDs
-
public final class QuickSelectDBIDs 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
- Since:
- 0.7.5
- Author:
- Erich Schubert
-
-
Field Summary
Fields Modifier and Type Field Description private static int
SMALL
For small arrays, use a simpler method:
-
Constructor Summary
Constructors Modifier Constructor Description private
QuickSelectDBIDs()
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(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int start, int end, DBIDArrayIter iter1, DBIDArrayIter iter2)
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.static int
median(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator)
Compute the median of an array efficiently using the QuickSelect method.static int
median(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, 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 int
quantile(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, double quant)
Compute the median of an array efficiently using the QuickSelect method.static int
quantile(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, 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 void
quickSelect(ArrayModifiableDBIDs data, java.util.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, java.util.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 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.
-
-
-
Field Detail
-
SMALL
private static final int SMALL
For small arrays, use a simpler method:- See Also:
- Constant Field Values
-
-
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 void quickSelect(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to userank
- Rank position that we are interested in (integer!)
-
median
public static int median(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to use- Returns:
- Median position
-
median
public static int median(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to usebegin
- Begin of valid valuesend
- End of valid values (exclusive!)- Returns:
- Median position
-
quantile
public static int quantile(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to usequant
- Quantile to compute- Returns:
- Quantile position
-
quantile
public static int quantile(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to usebegin
- Begin of valid valuesend
- End of valid values (exclusive)quant
- Quantile to compute- Returns:
- Quantile position
-
quickSelect
public static void quickSelect(ArrayModifiableDBIDs data, java.util.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 processcomparator
- Comparator to usestart
- Interval startend
- Interval end (exclusive)rank
- rank position we are interested in (starting at 0)
-
insertionSort
private static void insertionSort(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int start, int end, DBIDArrayIter iter1, DBIDArrayIter iter2)
Sort a small array using repetitive insertion sort.- Parameters:
data
- Data to sortstart
- Interval startend
- 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 processrank
- 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 processbegin
- Begin of valid valuesend
- 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 processquant
- 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 processbegin
- Begin of valid valuesend
- 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 processstart
- Interval startend
- 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 sortstart
- Interval startend
- Interval end
-
-