Class DoubleIntegerArrayQuickSort


  • public final class DoubleIntegerArrayQuickSort
    extends java.lang.Object
    Class to sort a double and an integer DBID array, using a quicksort with a best of 5 heuristic.
    Since:
    0.6.0
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static int INSERTION_THRESHOLD
      Threshold for using insertion sort.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      private static void insertionSort​(double[] keys, int[] vals, int start, int end)
      Sort via insertion sort.
      private static void insertionSortReverse​(double[] keys, int[] vals, int start, int end)
      Sort via insertion sort.
      private static void quickSort​(double[] keys, int[] vals, int start, int end)
      Actual recursive sort function.
      private static void quickSortReverse​(double[] keys, int[] vals, int start, int end)
      Actual recursive sort function.
      static void sort​(double[] keys, int[] values, int len)
      Sort the full array using the given comparator.
      static void sort​(double[] keys, int[] values, int start, int end)
      Sort the array using the given comparator.
      private static void sort5​(double[] keys, int[] vals, int m1, int m2, int m3, int m4, int m5)
      An explicit sort, for the five pivot candidates.
      static void sortReverse​(double[] keys, int[] values, int len)
      Sort the full array using the given comparator.
      static void sortReverse​(double[] keys, int[] values, int start, int end)
      Sort the array using the given comparator.
      private static void sortReverse5​(double[] keys, int[] vals, int m1, int m2, int m3, int m4, int m5)
      An explicit sort, for the five pivot candidates.
      private static void swap​(double[] keys, int[] vals, int j, int i)
      Swap two entries.
      • Methods inherited from class java.lang.Object

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

      • INSERTION_THRESHOLD

        private static final int INSERTION_THRESHOLD
        Threshold for using insertion sort.
        See Also:
        Constant Field Values
    • Constructor Detail

      • DoubleIntegerArrayQuickSort

        private DoubleIntegerArrayQuickSort()
        Private constructor. Static methods only.
    • Method Detail

      • sort

        public static void sort​(double[] keys,
                                int[] values,
                                int len)
        Sort the full array using the given comparator.
        Parameters:
        keys - Keys for sorting
        values - Values for sorting
        len - Length to sort.
      • sort

        public static void sort​(double[] keys,
                                int[] values,
                                int start,
                                int end)
        Sort the array using the given comparator.
        Parameters:
        keys - Keys for sorting
        values - Values for sorting
        start - First index
        end - Last index (exclusive)
      • quickSort

        private static void quickSort​(double[] keys,
                                      int[] vals,
                                      int start,
                                      int end)
        Actual recursive sort function.
        Parameters:
        keys - Keys for sorting
        vals - Values for sorting
        start - First index
        end - Last index (exclusive!)
      • sort5

        private static void sort5​(double[] keys,
                                  int[] vals,
                                  int m1,
                                  int m2,
                                  int m3,
                                  int m4,
                                  int m5)
        An explicit sort, for the five pivot candidates.

        Note that this must only be used with m1 < m2 < m3 < m4 < m5.

        Parameters:
        keys - Keys
        vals - Values
        m1 - Pivot candidate position
        m2 - Pivot candidate position
        m3 - Pivot candidate position
        m4 - Pivot candidate position
        m5 - Pivot candidate position
      • insertionSort

        private static void insertionSort​(double[] keys,
                                          int[] vals,
                                          int start,
                                          int end)
        Sort via insertion sort.
        Parameters:
        keys - Keys
        vals - Values
        start - Interval start
        end - Interval end
      • sortReverse

        public static void sortReverse​(double[] keys,
                                       int[] values,
                                       int len)
        Sort the full array using the given comparator.
        Parameters:
        keys - Keys for sorting
        values - Values for sorting
        len - Length to sort.
      • sortReverse

        public static void sortReverse​(double[] keys,
                                       int[] values,
                                       int start,
                                       int end)
        Sort the array using the given comparator.
        Parameters:
        keys - Keys for sorting
        values - Values for sorting
        start - First index
        end - Last index (exclusive)
      • quickSortReverse

        private static void quickSortReverse​(double[] keys,
                                             int[] vals,
                                             int start,
                                             int end)
        Actual recursive sort function.
        Parameters:
        keys - Keys for sorting
        vals - Values for sorting
        start - First index
        end - Last index (exclusive!)
      • sortReverse5

        private static void sortReverse5​(double[] keys,
                                         int[] vals,
                                         int m1,
                                         int m2,
                                         int m3,
                                         int m4,
                                         int m5)
        An explicit sort, for the five pivot candidates.

        Note that this must only be used with m1 < m2 < m3 < m4 < m5.

        Parameters:
        keys - Keys
        vals - Values
        m1 - Pivot candidate position
        m2 - Pivot candidate position
        m3 - Pivot candidate position
        m4 - Pivot candidate position
        m5 - Pivot candidate position
      • insertionSortReverse

        private static void insertionSortReverse​(double[] keys,
                                                 int[] vals,
                                                 int start,
                                                 int end)
        Sort via insertion sort.
        Parameters:
        keys - Keys
        vals - Values
        start - Interval start
        end - Interval end
      • swap

        private static void swap​(double[] keys,
                                 int[] vals,
                                 int j,
                                 int i)
        Swap two entries.
        Parameters:
        keys - Keys
        vals - Values
        j - First index
        i - Second index