Package smile.sort

# Interface QuickSelect

public interface QuickSelect
Selection is asking for the k-th smallest element out of n elements. This class implements the fastest general method for selection based on partitioning, exactly as done in the Quicksort algorithm.

The most common use of selection is in the statistical characterization of a set of data. One often wants to know the median element (quantile p = 1/2) in an array or the top and bottom quartile elements (quantile p = 1/4, 3/4).

• ## Method Summary

Static Methods
Modifier and Type
Method
Description
`static double`
`median(double[] x)`
Find the median of an array of type double.
`static float`
`median(float[] x)`
Find the median of an array of type float.
`static int`
`median(int[] x)`
Find the median of an array of type integer.
`static <T extends Comparable<? super T>>T`
`median(T[] x)`
Find the median of an array of type double.
`static double`
`q1(double[] x)`
Find the first quantile (p = 1/4) of an array of type double.
`static float`
`q1(float[] x)`
Find the first quantile (p = 1/4) of an array of type float.
`static int`
`q1(int[] x)`
Find the first quantile (p = 1/4) of an array of type integer.
`static <T extends Comparable<? super T>>T`
`q1(T[] x)`
Find the first quantile (p = 1/4) of an array of type double.
`static double`
`q3(double[] x)`
Find the third quantile (p = 3/4) of an array of type double.
`static float`
`q3(float[] x)`
Find the third quantile (p = 3/4) of an array of type float.
`static int`
`q3(int[] x)`
Find the third quantile (p = 3/4) of an array of type integer.
`static <T extends Comparable<? super T>>T`
`q3(T[] x)`
Find the third quantile (p = 3/4) of an array of type double.
`static double`
```select(double[] x, int k)```
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned.
`static float`
```select(float[] x, int k)```
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned.
`static int`
```select(int[] x, int k)```
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned.
`static <T extends Comparable<? super T>>T`
```select(T[] x, int k)```
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned.
• ## Method Details

• ### select

static int select(int[] x, int k)
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned. The input array will be rearranged to have this value in location x[k], with all smaller elements moved to x[0, k-1] (in arbitrary order) and all larger elements in x[k+1, n-1] (also in arbitrary order).
Parameters:
`x` - the array.
`k` - the ordinal index.
Returns:
the k-th smalles value.
• ### select

static float select(float[] x, int k)
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned. The input array will be rearranged to have this value in location x[k], with all smaller elements moved to x[0, k-1] (in arbitrary order) and all larger elements in x[k+1, n-1] (also in arbitrary order).
Parameters:
`x` - the array.
`k` - the ordinal index.
Returns:
the k-th smalles value.
• ### select

static double select(double[] x, int k)
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned. The input array will be rearranged to have this value in location x[k], with all smaller elements moved to x[0, k-1] (in arbitrary order) and all larger elements in x[k+1, n-1] (also in arbitrary order).
Parameters:
`x` - the array.
`k` - the ordinal index.
Returns:
the k-th smalles value.
• ### select

static <T extends Comparable<? super T>> T select(T[] x, int k)
Given k in [0, n-1], returns an array value from arr such that k array values are less than or equal to the one returned. The input array will be rearranged to have this value in location x[k], with all smaller elements moved to x[0, k-1] (in arbitrary order) and all larger elements in x[k+1, n-1] (also in arbitrary order).
Type Parameters:
`T` - the data type of array elements.
Parameters:
`x` - the array.
`k` - the ordinal index.
Returns:
the k-th smalles value.
• ### median

static int median(int[] x)
Find the median of an array of type integer.
Parameters:
`x` - the array.
Returns:
the median.
• ### median

static float median(float[] x)
Find the median of an array of type float.
Parameters:
`x` - the array.
Returns:
the median.
• ### median

static double median(double[] x)
Find the median of an array of type double.
Parameters:
`x` - the array.
Returns:
the median.
• ### median

static <T extends Comparable<? super T>> T median(T[] x)
Find the median of an array of type double.
Type Parameters:
`T` - the data type of array elements.
Parameters:
`x` - the array.
Returns:
the median.
• ### q1

static int q1(int[] x)
Find the first quantile (p = 1/4) of an array of type integer.
Parameters:
`x` - the array.
Returns:
the first quantile.
• ### q1

static float q1(float[] x)
Find the first quantile (p = 1/4) of an array of type float.
Parameters:
`x` - the array.
Returns:
the first quantile.
• ### q1

static double q1(double[] x)
Find the first quantile (p = 1/4) of an array of type double.
Parameters:
`x` - the array.
Returns:
the first quantile.
• ### q1

static <T extends Comparable<? super T>> T q1(T[] x)
Find the first quantile (p = 1/4) of an array of type double.
Type Parameters:
`T` - the data type of array elements.
Parameters:
`x` - the array.
Returns:
the first quantile.
• ### q3

static int q3(int[] x)
Find the third quantile (p = 3/4) of an array of type integer.
Parameters:
`x` - the array.
Returns:
the third quantile.
• ### q3

static float q3(float[] x)
Find the third quantile (p = 3/4) of an array of type float.
Parameters:
`x` - the array.
Returns:
the third quantile.
• ### q3

static double q3(double[] x)
Find the third quantile (p = 3/4) of an array of type double.
Parameters:
`x` - the array.
Returns:
the third quantile.
• ### q3

static <T extends Comparable<? super T>> T q3(T[] x)
Find the third quantile (p = 3/4) of an array of type double.
Type Parameters:
`T` - the data type of array elements.
Parameters:
`x` - the array.
Returns:
the third quantile.