public class QuickSelect extends Object
| Modifier and Type | Field and Description |
|---|---|
private static int |
SMALL
For small arrays, use a simpler method:
|
| Constructor and Description |
|---|
QuickSelect() |
| Modifier and Type | Method and Description |
|---|---|
private static void |
insertionSort(ArrayModifiableDBIDs data,
Comparator<? super DBID> 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>> |
insertionSort(List<T> data,
int start,
int end)
Sort a small array using repetitive insertion sort.
|
private static <T extends Comparable<? super T>> |
insertionSort(T[] data,
int start,
int end)
Sort a small array using repetitive insertion sort.
|
static DBID |
median(ArrayModifiableDBIDs data,
Comparator<? super DBID> comparator)
Compute the median of an array efficiently using the QuickSelect method.
|
static DBID |
median(ArrayModifiableDBIDs data,
Comparator<? super DBID> 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>> |
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>> |
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>> |
median(T[] data)
Compute the median of an array efficiently using the QuickSelect method.
|
static <T extends Comparable<? super 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 DBID> comparator,
double quant)
Compute the median of an array efficiently using the QuickSelect method.
|
static DBID |
quantile(ArrayModifiableDBIDs data,
Comparator<? super DBID> 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>> |
quantile(List<? extends T> data,
double quant)
Compute the median of an array efficiently using the QuickSelect method.
|
static <T extends Comparable<? super 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>> |
quantile(T[] data,
double quant)
Compute the median of an array efficiently using the QuickSelect method.
|
static <T extends Comparable<? super 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 DBID> 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 DBID> 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>> |
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>> |
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>> |
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>> |
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>> |
swap(T[] data,
int a,
int b)
The usual swap method.
|
private static final int SMALL
public static double quickSelect(double[] data,
int rank)
data - Data to processrank - Rank position that we are interested in (integer!)public static double median(double[] data)
data - Data to processpublic static double median(double[] data,
int begin,
int end)
data - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)public static double quantile(double[] data,
double quant)
data - Data to processquant - Quantile to computepublic static double quantile(double[] data,
int begin,
int end,
double quant)
data - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)quant - Quantile to computepublic static void quickSelect(double[] data,
int start,
int end,
int rank)
data - Data to processstart - Interval startend - Interval end (exclusive)rank - rank position we are interested in (starting at 0)private static void insertionSort(double[] data,
int start,
int end)
data - Data to sortstart - Interval startend - Interval endprivate static final void swap(double[] data,
int a,
int b)
data - Arraya - First indexb - Second indexpublic static <T extends Comparable<? super T>> T quickSelect(T[] data, int rank)
T - object typedata - Data to processrank - Rank position that we are interested in (integer!)public static <T extends Comparable<? super T>> T median(T[] data)
data - Data to processpublic static <T extends Comparable<? super T>> T median(T[] data, int begin, int end)
T - object typedata - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)public static <T extends Comparable<? super T>> T quantile(T[] data, double quant)
T - object typedata - Data to processquant - Quantile to computepublic static <T extends Comparable<? super T>> T quantile(T[] data, int begin, int end, double quant)
T - object typedata - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)quant - Quantile to computepublic static <T extends Comparable<? super T>> void quickSelect(T[] data, int start, int end, int rank)
T - object typedata - Data to processstart - Interval startend - Interval end (exclusive)rank - rank position we are interested in (starting at 0)private static <T extends Comparable<? super T>> void insertionSort(T[] data, int start, int end)
T - object typedata - Data to sortstart - Interval startend - Interval endprivate static final <T extends Comparable<? super T>> void swap(T[] data, int a, int b)
T - object typedata - Arraya - First indexb - Second indexpublic static <T extends Comparable<? super T>> T quickSelect(List<? extends T> data, int rank)
T - object typedata - Data to processrank - Rank position that we are interested in (integer!)public static <T extends Comparable<? super T>> T median(List<? extends T> data)
T - object typedata - Data to processpublic static <T extends Comparable<? super T>> T median(List<? extends T> data, int begin, int end)
T - object typedata - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)public static <T extends Comparable<? super T>> T quantile(List<? extends T> data, double quant)
T - object typedata - Data to processquant - Quantile to computepublic static <T extends Comparable<? super T>> T quantile(List<? extends T> data, int begin, int end, double quant)
T - object typedata - Data to processbegin - Begin of valid valuesend - End of valid values (exclusive!)quant - Quantile to computepublic static <T extends Comparable<? super T>> void quickSelect(List<? extends T> data, int start, int end, int rank)
T - object typedata - Data to processstart - Interval startend - Interval end (exclusive)rank - rank position we are interested in (starting at 0)private static <T extends Comparable<? super T>> void insertionSort(List<T> data, int start, int end)
T - object typedata - Data to sortstart - Interval startend - Interval endprivate static final <T> void swap(List<T> data, int a, int b)
T - object typedata - Arraya - First indexb - Second indexpublic static <T> T quickSelect(List<? extends T> data, Comparator<? super T> comparator, int rank)
T - object typedata - Data to processcomparator - Comparator to userank - Rank position that we are interested in (integer!)public static <T> T median(List<? extends T> data, Comparator<? super T> comparator)
T - object typedata - Data to processcomparator - Comparator to usepublic static <T> T median(List<? extends T> data, Comparator<? super T> comparator, int begin, int end)
T - object typedata - Data to processcomparator - Comparator to usebegin - Begin of valid valuesend - End of valid values (exclusive!)public static <T> T quantile(List<? extends T> data, Comparator<? super T> comparator, double quant)
T - object typedata - Data to processcomparator - Comparator to usequant - Quantile to computepublic static <T> T quantile(List<? extends T> data, Comparator<? super T> comparator, int begin, int end, double quant)
T - object typedata - Data to processcomparator - Comparator to usebegin - Begin of valid valuesend - End of valid values (inclusive!)quant - Quantile to computepublic static <T> void quickSelect(List<? extends T> data, Comparator<? super T> comparator, int start, int end, int rank)
T - object typedata - Data to processcomparator - Comparator to usestart - Interval startend - Interval end (inclusive)rank - rank position we are interested in (starting at 0)private static <T> void insertionSort(List<T> data, Comparator<? super T> comparator, int start, int end)
T - object typedata - Data to sortstart - Interval startend - Interval endpublic static DBID quickSelect(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, int rank)
data - Data to processcomparator - Comparator to userank - Rank position that we are interested in (integer!)public static DBID median(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator)
data - Data to processcomparator - Comparator to usepublic static DBID median(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, int begin, int end)
data - Data to processcomparator - Comparator to usebegin - Begin of valid valuesend - End of valid values (exclusive!)public static DBID quantile(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, double quant)
data - Data to processcomparator - Comparator to usequant - Quantile to computepublic static DBID quantile(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, int begin, int end, double quant)
data - Data to processcomparator - Comparator to usebegin - Begin of valid valuesend - End of valid values (inclusive!)quant - Quantile to computepublic static void quickSelect(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, int start, int end, int rank)
data - Data to processcomparator - Comparator to usestart - Interval startend - Interval end (inclusive)rank - rank position we are interested in (starting at 0)private static void insertionSort(ArrayModifiableDBIDs data, Comparator<? super DBID> comparator, int start, int end)
data - Data to sortstart - Interval startend - Interval end