Package smile.sort
Class QuickSelect
- java.lang.Object
-
- smile.sort.QuickSelect
-
public class QuickSelect extends java.lang.Object
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).
- Author:
- Haifeng Li
-
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static double
median(double[] a)
Find the median of an array of type double.static float
median(float[] a)
Find the median of an array of type float.static int
median(int[] a)
Find the median of an array of type integer.static <T extends java.lang.Comparable<? super T>>
Tmedian(T[] a)
Find the median of an array of type double.static double
q1(double[] a)
Find the first quantile (p = 1/4) of an array of type double.static float
q1(float[] a)
Find the first quantile (p = 1/4) of an array of type float.static int
q1(int[] a)
Find the first quantile (p = 1/4) of an array of type integer.static <T extends java.lang.Comparable<? super T>>
Tq1(T[] a)
Find the first quantile (p = 1/4) of an array of type double.static double
q3(double[] a)
Find the third quantile (p = 3/4) of an array of type double.static float
q3(float[] a)
Find the third quantile (p = 3/4) of an array of type float.static int
q3(int[] a)
Find the third quantile (p = 3/4) of an array of type integer.static <T extends java.lang.Comparable<? super T>>
Tq3(T[] a)
Find the third quantile (p = 3/4) of an array of type double.static double
select(double[] arr, 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[] arr, 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[] arr, 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 java.lang.Comparable<? super T>>
Tselect(T[] arr, 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 Detail
-
select
public static int select(int[] arr, 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 arr[k], with all smaller elements moved to arr[0, k-1] (in arbitrary order) and all larger elements in arr[k+1, n-1] (also in arbitrary order).
-
select
public static float select(float[] arr, 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 arr[k], with all smaller elements moved to arr[0, k-1] (in arbitrary order) and all larger elements in arr[k+1, n-1] (also in arbitrary order).
-
select
public static double select(double[] arr, 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 arr[k], with all smaller elements moved to arr[0, k-1] (in arbitrary order) and all larger elements in arr[k+1, n-1] (also in arbitrary order).
-
select
public static <T extends java.lang.Comparable<? super T>> T select(T[] arr, 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 arr[k], with all smaller elements moved to arr[0, k-1] (in arbitrary order) and all larger elements in arr[k+1, n-1] (also in arbitrary order).
-
median
public static int median(int[] a)
Find the median of an array of type integer.
-
median
public static float median(float[] a)
Find the median of an array of type float.
-
median
public static double median(double[] a)
Find the median of an array of type double.
-
median
public static <T extends java.lang.Comparable<? super T>> T median(T[] a)
Find the median of an array of type double.
-
q1
public static int q1(int[] a)
Find the first quantile (p = 1/4) of an array of type integer.
-
q1
public static float q1(float[] a)
Find the first quantile (p = 1/4) of an array of type float.
-
q1
public static double q1(double[] a)
Find the first quantile (p = 1/4) of an array of type double.
-
q1
public static <T extends java.lang.Comparable<? super T>> T q1(T[] a)
Find the first quantile (p = 1/4) of an array of type double.
-
q3
public static int q3(int[] a)
Find the third quantile (p = 3/4) of an array of type integer.
-
q3
public static float q3(float[] a)
Find the third quantile (p = 3/4) of an array of type float.
-
q3
public static double q3(double[] a)
Find the third quantile (p = 3/4) of an array of type double.
-
q3
public static <T extends java.lang.Comparable<? super T>> T q3(T[] a)
Find the third quantile (p = 3/4) of an array of type double.
-
-