Package com.tdunning.math.stats

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