Class Sort

java.lang.Object
com.tdunning.math.stats.Sort

public class Sort extends Object
Static sorting methods
  • Constructor Summary

    Constructors
    Constructor
    Description
     
  • Method Summary

    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 Details

    • Sort

      public Sort()
  • Method Details

    • 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