Package com.tdunning.math.stats
Class Sort
java.lang.Object
com.tdunning.math.stats.Sort
Static sorting methods
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic 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 themselvesstatic 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)
-
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 valuesvalues
- 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 valuesvalues
- 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 arrayvalues
- The values to sortstart
- The beginning of the values to sortend
- The value after the last value to sortlimit
- 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 indexvalues
- The values we are sortinglimit
- The largest amount of disorder
-