Package smile.sort

Class 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>>
      T
      median​(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>>
      T
      q1​(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>>
      T
      q3​(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>>
      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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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.