Class Sort


  • public class Sort
    extends java.lang.Object
    Static sorting methods
    • Constructor Summary

      Constructors 
      Constructor Description
      Sort()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static void checkPartition​(int[] order, double[] values, double pivotValue, int start, int low, int high, int end)
      Check that a partition step was done correctly.
      private static void insertionSort​(int[] order, double[] values, int n, int limit)
      Limited range insertion sort.
      private static void quickSort​(int[] order, double[] values, int start, int end, int limit)
      Standard quick sort except that sorting is done on an index array rather than the values themselves
      static void sort​(int[] order, double[] values)
      Quick sort using an index array.
      static void sort​(int[] order, double[] values, int n)
      Quick sort using an index array.
      private static void swap​(int[] order, int i, int j)  
      • Methods inherited from class java.lang.Object

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

      • Sort

        public Sort()
    • Method Detail

      • sort

        public static void sort​(int[] order,
                                double[] values)
        Quick sort using an index array. On return, the values[order[i]] is in order as i goes 0..values.length
        Parameters:
        order - Indexes into values
        values - The values to sort.
      • sort

        public static void sort​(int[] order,
                                double[] values,
                                int n)
        Quick sort using an index array. On return, the values[order[i]] is in order as i goes 0..values.length
        Parameters:
        order - Indexes into values
        values - The values to sort.
        n - The number of values to sort
      • quickSort

        private static void quickSort​(int[] order,
                                      double[] values,
                                      int start,
                                      int end,
                                      int limit)
        Standard quick sort except that sorting is done on an index array rather than the values themselves
        Parameters:
        order - The pre-allocated index array
        values - The values to sort
        start - The beginning of the values to sort
        end - The value after the last value to sort
        limit - The minimum size to recurse down to.
      • swap

        private static void swap​(int[] order,
                                 int i,
                                 int j)
      • checkPartition

        public static void checkPartition​(int[] order,
                                          double[] values,
                                          double pivotValue,
                                          int start,
                                          int low,
                                          int high,
                                          int end)
        Check that a partition step was done correctly. For debugging and testing.
      • insertionSort

        private static void insertionSort​(int[] order,
                                          double[] values,
                                          int n,
                                          int limit)
        Limited range insertion sort. We assume that no element has to move more than limit steps because quick sort has done its thing.
        Parameters:
        order - The permutation index
        values - The values we are sorting
        limit - The largest amount of disorder