Class QuickSelect


  • public class QuickSelect
    extends java.lang.Object
    QuickSelect computes ("selects") the element at a given rank and can be used to compute Medians and arbitrary quantiles by computing the appropriate rank.

    This algorithm is essentially an incomplete QuickSort that only descends into that part of the data that we are interested in, and also attributed to Charles Antony Richard Hoare.

    If you want to use this with a Comparable type, use the natural comparator Comparator.naturalOrder(). You can wrap arrays as lists with java.util.Arrays#asList, to sort them in-place, or implement an QuickSelect.Adapter for your data structure.

    Since:
    0.4.0
    Author:
    Erich Schubert
    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      static interface  QuickSelect.Adapter<T>
      Adapter class to apply QuickSelect to arbitrary data structures.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private QuickSelect()
      Do not instantiate - static methods only!
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static int bestPivot​(int rank, int m1, int m2, int m3, int m4, int m5)
      Choose the best pivot for the given rank.
      private static void insertionSort​(double[] data, int start, int end)
      Sort a small array using repetitive insertion sort.
      private static <T> void insertionSort​(java.util.List<T> data, java.util.Comparator<? super T> comparator, int start, int end)
      Sort a small array using repetitive insertion sort.
      private static <T> void insertionSort​(T data, QuickSelect.Adapter<T> adapter, int start, int end)
      Sort a small array using repetitive insertion sort.
      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> T median​(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator)
      Compute the median of an array efficiently using the QuickSelect method.
      static <T> T median​(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, int begin, int end)
      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​(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      static <T> T quantile​(java.util.List<? extends T> data, java.util.Comparator<? super T> comparator, int begin, int end, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      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 double 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​(java.util.List<? extends T> data, java.util.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​(java.util.List<? extends T> data, java.util.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> void quickSelect​(T data, QuickSelect.Adapter<T> adapter, 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​(java.util.List<T> data, int a, int b)
      The usual swap method.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • SMALL

        private static final int SMALL
        For small arrays, use a simpler method:
        See Also:
        Constant Field Values
      • DOUBLE_ADAPTER

        public static final QuickSelect.Adapter<double[]> DOUBLE_ADAPTER
        Adapter for double arrays.
      • INTEGER_ADAPTER

        public static final QuickSelect.Adapter<int[]> INTEGER_ADAPTER
        Adapter for integer arrays.
      • FLOAT_ADAPTER

        public static final QuickSelect.Adapter<float[]> FLOAT_ADAPTER
        Adapter for float arrays.
      • SHORT_ADAPTER

        public static final QuickSelect.Adapter<short[]> SHORT_ADAPTER
        Adapter for short arrays.
      • LONG_ADAPTER

        public static final QuickSelect.Adapter<long[]> LONG_ADAPTER
        Adapter for long arrays.
      • BYTE_ADAPTER

        public static final QuickSelect.Adapter<byte[]> BYTE_ADAPTER
        Adapter for byte arrays.
      • CHAR_ADAPTER

        public static final QuickSelect.Adapter<char[]> CHAR_ADAPTER
        Adapter for char arrays.
    • Constructor Detail

      • QuickSelect

        private QuickSelect()
        Do not instantiate - static methods only!
    • Method Detail

      • bestPivot

        private static int bestPivot​(int rank,
                                     int m1,
                                     int m2,
                                     int m3,
                                     int m4,
                                     int m5)
        Choose the best pivot for the given rank.
        Parameters:
        rank - Rank
        m1 - Pivot candidate
        m2 - Pivot candidate
        m3 - Pivot candidate
        m4 - Pivot candidate
        m5 - Pivot candidate
        Returns:
        Best pivot candidate
      • quickSelect

        public static <T> void quickSelect​(T data,
                                           QuickSelect.Adapter<T> adapter,
                                           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.
        Parameters:
        data - Data to process
        start - Interval start
        end - Interval end (exclusive)
        rank - rank position we are interested in (starting at 0)
      • insertionSort

        private static <T> void insertionSort​(T data,
                                              QuickSelect.Adapter<T> adapter,
                                              int start,
                                              int end)
        Sort a small array using repetitive insertion sort.
        Parameters:
        data - Data to sort
        start - Interval start
        end - Interval end
      • quickSelect

        public 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. Note: the array is modified by this.
        Parameters:
        data - Data to process
        rank - Rank position that we are interested in (integer!)
        Returns:
        Value at the given rank
      • median

        public static double median​(double[] data)
        Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
        Parameters:
        data - Data to process
        Returns:
        Median value
      • median

        public static double median​(double[] data,
                                    int begin,
                                    int end)
        Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
        Parameters:
        data - Data to process
        begin - Begin of valid values
        end - End of valid values (exclusive!)
        Returns:
        Median value
      • quantile

        public static double quantile​(double[] data,
                                      double quant)
        Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
        Parameters:
        data - Data to process
        quant - Quantile to compute
        Returns:
        Value at quantile
      • quantile

        public static double quantile​(double[] data,
                                      int begin,
                                      int end,
                                      double quant)
        Compute the median of an array efficiently using the QuickSelect method. Note: the array is modified by this.
        Parameters:
        data - Data to process
        begin - Begin of valid values
        end - End of valid values (exclusive!)
        quant - Quantile to compute
        Returns:
        Value at quantile
      • quickSelect

        public static double 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.
        Parameters:
        data - Data to process
        start - Interval start
        end - Interval end (exclusive)
        rank - rank position we are interested in (starting at 0)
        Returns:
        Element at the given rank (starting at 0).
      • insertionSort

        private static void insertionSort​(double[] data,
                                          int start,
                                          int end)
        Sort a small array using repetitive insertion sort.
        Parameters:
        data - Data to sort
        start - Interval start
        end - Interval end
      • swap

        private static void swap​(double[] data,
                                 int a,
                                 int b)
        The usual swap method.
        Parameters:
        data - Array
        a - First index
        b - Second index
      • swap

        private static <T> void swap​(java.util.List<T> data,
                                     int a,
                                     int b)
        The usual swap method.
        Type Parameters:
        T - object type
        Parameters:
        data - Array
        a - First index
        b - Second index
      • quickSelect

        public static <T> T quickSelect​(java.util.List<? extends T> data,
                                        java.util.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.

        Note: the array is modified by this.

        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        rank - Rank position that we are interested in (integer!)
        Returns:
        Value at the given rank
      • median

        public static <T> T median​(java.util.List<? extends T> data,
                                   java.util.Comparator<? super T> comparator)
        Compute the median of an array efficiently using the QuickSelect method.

        Note: the array is modified by this.

        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        Returns:
        Median value
      • median

        public static <T> T median​(java.util.List<? extends T> data,
                                   java.util.Comparator<? super T> comparator,
                                   int begin,
                                   int end)
        Compute the median of an array efficiently using the QuickSelect method.

        On an odd length, it will return the lower element.

        Note: the array is modified by this.

        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        begin - Begin of valid values
        end - End of valid values (exclusive!)
        Returns:
        Median value
      • quantile

        public static <T> T quantile​(java.util.List<? extends T> data,
                                     java.util.Comparator<? super T> comparator,
                                     double quant)
        Compute the median of an array efficiently using the QuickSelect method.

        Note: the array is modified by this.

        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        quant - Quantile to compute
        Returns:
        Value at quantile
      • quantile

        public static <T> T quantile​(java.util.List<? extends T> data,
                                     java.util.Comparator<? super T> comparator,
                                     int begin,
                                     int end,
                                     double quant)
        Compute the median of an array efficiently using the QuickSelect method.

        It will prefer the lower element.

        Note: the array is modified by this.

        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        begin - Begin of valid values
        end - End of valid values (inclusive!)
        quant - Quantile to compute
        Returns:
        Value at quantile
      • quickSelect

        public static <T> void quickSelect​(java.util.List<? extends T> data,
                                           java.util.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.
        Type Parameters:
        T - object type
        Parameters:
        data - Data to process
        comparator - Comparator to use
        start - Interval start
        end - Interval end (inclusive)
        rank - rank position we are interested in (starting at 0)
      • insertionSort

        private static <T> void insertionSort​(java.util.List<T> data,
                                              java.util.Comparator<? super T> comparator,
                                              int start,
                                              int end)
        Sort a small array using repetitive insertion sort.
        Type Parameters:
        T - object type
        Parameters:
        data - Data to sort
        start - Interval start
        end - Interval end