Class QuickSelectDBIDs


  • public final class QuickSelectDBIDs
    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

    Since:
    0.7.5
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int SMALL
      For small arrays, use a simpler method:
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private QuickSelectDBIDs()
      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​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int start, int end, DBIDArrayIter iter1, DBIDArrayIter iter2)
      Sort a small array using repetitive insertion sort.
      private static void insertionSort​(ModifiableDoubleDBIDList data, int start, int end, DoubleDBIDListIter iter1, DoubleDBIDListIter iter2)
      Sort a small array using repetitive insertion sort.
      static int median​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator)
      Compute the median of an array efficiently using the QuickSelect method.
      static int median​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int begin, int end)
      Compute the median of an array efficiently using the QuickSelect method.
      static int median​(ModifiableDoubleDBIDList data)
      Compute the median of an array efficiently using the QuickSelect method.
      static int median​(ModifiableDoubleDBIDList data, int begin, int end)
      Compute the median of an array efficiently using the QuickSelect method.
      static int quantile​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      static int quantile​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int begin, int end, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      static int quantile​(ModifiableDoubleDBIDList data, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      static int quantile​(ModifiableDoubleDBIDList data, int begin, int end, double quant)
      Compute the median of an array efficiently using the QuickSelect method.
      static void quickSelect​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> comparator, int rank)
      QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
      static void quickSelect​(ArrayModifiableDBIDs data, java.util.Comparator<? super DBIDRef> 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 void quickSelect​(ModifiableDoubleDBIDList data, int rank)
      QuickSelect is essentially quicksort, except that we only "sort" that half of the array that we are interested in.
      static void quickSelect​(ModifiableDoubleDBIDList 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.
      • 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
    • Constructor Detail

      • QuickSelectDBIDs

        private QuickSelectDBIDs()
        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 void quickSelect​(ArrayModifiableDBIDs data,
                                       java.util.Comparator<? super DBIDRef> 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.
        Parameters:
        data - Data to process
        comparator - Comparator to use
        rank - Rank position that we are interested in (integer!)
      • median

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

        Note: the array is modified by this.

        Parameters:
        data - Data to process
        comparator - Comparator to use
        Returns:
        Median position
      • median

        public static int median​(ArrayModifiableDBIDs data,
                                 java.util.Comparator<? super DBIDRef> 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.

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

        public static int quantile​(ArrayModifiableDBIDs data,
                                   java.util.Comparator<? super DBIDRef> comparator,
                                   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
        comparator - Comparator to use
        quant - Quantile to compute
        Returns:
        Quantile position
      • quantile

        public static int quantile​(ArrayModifiableDBIDs data,
                                   java.util.Comparator<? super DBIDRef> 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.

        Parameters:
        data - Data to process
        comparator - Comparator to use
        begin - Begin of valid values
        end - End of valid values (exclusive)
        quant - Quantile to compute
        Returns:
        Quantile position
      • quickSelect

        public static void quickSelect​(ArrayModifiableDBIDs data,
                                       java.util.Comparator<? super DBIDRef> 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.
        Parameters:
        data - Data to process
        comparator - Comparator to use
        start - Interval start
        end - Interval end (exclusive)
        rank - rank position we are interested in (starting at 0)
      • insertionSort

        private static void insertionSort​(ArrayModifiableDBIDs data,
                                          java.util.Comparator<? super DBIDRef> comparator,
                                          int start,
                                          int end,
                                          DBIDArrayIter iter1,
                                          DBIDArrayIter iter2)
        Sort a small array using repetitive insertion sort.
        Parameters:
        data - Data to sort
        start - Interval start
        end - Interval end
      • quickSelect

        public static void quickSelect​(ModifiableDoubleDBIDList 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!)
      • median

        public static int median​(ModifiableDoubleDBIDList 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 position
      • median

        public static int median​(ModifiableDoubleDBIDList data,
                                 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.

        Parameters:
        data - Data to process
        begin - Begin of valid values
        end - End of valid values (exclusive!)
        Returns:
        Median position
      • quantile

        public static int quantile​(ModifiableDoubleDBIDList 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:
        Quantile position
      • quantile

        public static int quantile​(ModifiableDoubleDBIDList data,
                                   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.

        Parameters:
        data - Data to process
        begin - Begin of valid values
        end - End of valid values (exclusive)
        quant - Quantile to compute
        Returns:
        Quantile position
      • quickSelect

        public static void quickSelect​(ModifiableDoubleDBIDList 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)