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.