6899694: Dual-pivot quicksort improvements
Reviewed-by: jjb
Contributed-by: vladimir.yaroslavskiy@sun.com, joshua.bloch@google.com
--- a/jdk/src/share/classes/java/util/Arrays.java Tue Nov 10 13:09:50 2009 +0000
+++ b/jdk/src/share/classes/java/util/Arrays.java Wed Nov 11 14:38:01 2009 +0000
@@ -57,51 +57,14 @@
// Suppresses default constructor, ensuring non-instantiability.
private Arrays() {}
- // Sorting
+ /*
+ * Sorting of primitive type arrays.
+ */
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
- * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
- * offers O(n log(n)) performance on many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
- * faster than traditional (one-pivot) Quicksort implementations.
- *
- * @param a the array to be sorted
- */
- public static void sort(long[] a) {
- sort(a, 0, a.length);
- }
-
- /**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
- * the range to be sorted is empty.
- *
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
- * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
- * offers O(n log(n)) performance on many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
- * faster than traditional (one-pivot) Quicksort implementations.
- *
- * @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
- * @throws IllegalArgumentException if {@code fromIndex > toIndex}
- * @throws ArrayIndexOutOfBoundsException
- * if {@code fromIndex < 0} or {@code toIndex > a.length}
- */
- public static void sort(long[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
- }
-
- /**
- * Sorts the specified array into ascending numerical order.
- *
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
@@ -110,37 +73,76 @@
* @param a the array to be sorted
*/
public static void sort(int[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a);
}
/**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(int[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+ * offers O(n log(n)) performance on many data sets that cause other
+ * quicksorts to degrade to quadratic performance, and is typically
+ * faster than traditional (one-pivot) Quicksort implementations.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(long[] a) {
+ DualPivotQuicksort.sort(a);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+ * offers O(n log(n)) performance on many data sets that cause other
+ * quicksorts to degrade to quadratic performance, and is typically
+ * faster than traditional (one-pivot) Quicksort implementations.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(long[] a, int fromIndex, int toIndex) {
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
@@ -149,37 +151,37 @@
* @param a the array to be sorted
*/
public static void sort(short[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a);
}
/**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(short[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
@@ -188,37 +190,37 @@
* @param a the array to be sorted
*/
public static void sort(char[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a);
}
/**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(char[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
@@ -227,49 +229,100 @@
* @param a the array to be sorted
*/
public static void sort(byte[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a);
}
/**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+ * offers O(n log(n)) performance on many data sets that cause other
+ * quicksorts to degrade to quadratic performance, and is typically
+ * faster than traditional (one-pivot) Quicksort implementations.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(byte[] a, int fromIndex, int toIndex) {
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
+ */
+ public static void sort(float[] a) {
+ DualPivotQuicksort.sort(a);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
+ * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
+ * offers O(n log(n)) performance on many data sets that cause other
+ * quicksorts to degrade to quadratic performance, and is typically
+ * faster than traditional (one-pivot) Quicksort implementations.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
- public static void sort(byte[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
+ public static void sort(float[] a, int fromIndex, int toIndex) {
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
/**
* Sorts the specified array into ascending numerical order.
*
- * <p>The {@code <} relation does not provide a total order on
- * all floating-point values; although they are distinct numbers
- * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares
- * neither less than, greater than, nor equal to any floating-point
- * value, even itself. To allow the sort to proceed, instead of using
- * the {@code <} relation to determine ascending numerical order,
- * this method uses the total order imposed by {@link Double#compareTo}.
- * This ordering differs from the {@code <} relation in that {@code -0.0d}
- * is treated as less than {@code 0.0d} and NaN is considered greater than
- * any other floating-point value. For the purposes of sorting, all NaN
- * values are considered equivalent and equal.
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
@@ -278,203 +331,45 @@
* @param a the array to be sorted
*/
public static void sort(double[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a);
}
/**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
* the range to be sorted is empty.
*
- * <p>The {@code <} relation does not provide a total order on
- * all floating-point values; although they are distinct numbers
- * {@code -0.0d == 0.0d} is {@code true} and a NaN value compares
- * neither less than, greater than, nor equal to any floating-point
- * value, even itself. To allow the sort to proceed, instead of using
- * the {@code <} relation to determine ascending numerical order,
- * this method uses the total order imposed by {@link Double#compareTo}.
- * This ordering differs from the {@code <} relation in that {@code -0.0d}
- * is treated as less than {@code 0.0d} and NaN is considered greater than
- * any other floating-point value. For the purposes of sorting, all NaN
- * values are considered equivalent and equal.
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
*
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
+ * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ *
* @throws IllegalArgumentException if {@code fromIndex > toIndex}
* @throws ArrayIndexOutOfBoundsException
* if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
public static void sort(double[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- sortNegZeroAndNaN(a, fromIndex, toIndex);
- }
-
- private static void sortNegZeroAndNaN(double[] a, int fromIndex, int toIndex) {
- final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
- /*
- * The sort is done in three phases to avoid the expense of using
- * NaN and -0.0d aware comparisons during the main sort.
- *
- * Preprocessing phase: move any NaN's to end of array, count the
- * number of -0.0d's, and turn them into 0.0d's.
- */
- int numNegZeros = 0;
- int i = fromIndex;
- int n = toIndex;
- double temp;
-
- while (i < n) {
- if (a[i] != a[i]) {
- n--;
- temp = a[i];
- a[i] = a[n];
- a[n] = temp;
- }
- else {
- if (a[i] == 0 && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) {
- a[i] = 0.0d;
- numNegZeros++;
- }
- i++;
- }
- }
- // Main sort phase: quicksort everything but the NaN's
- DualPivotQuicksort.sort(a, fromIndex, n - 1);
-
- // Postprocessing phase: change 0.0d's to -0.0d's as required
- if (numNegZeros != 0) {
- int j = binarySearch0(a, fromIndex, n, 0.0d); // position of ANY zero
-
- do {
- j--;
- }
- while (j >= fromIndex && a[j] == 0.0d);
-
- // j is now one less than the index of the FIRST zero
- for (int k = 0; k < numNegZeros; k++) {
- a[++j] = -0.0d;
- }
- }
- }
-
- /**
- * Sorts the specified array into ascending numerical order.
- *
- * <p>The {@code <} relation does not provide a total order on
- * all floating-point values; although they are distinct numbers
- * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares
- * neither less than, greater than, nor equal to any floating-point
- * value, even itself. To allow the sort to proceed, instead of using
- * the {@code <} relation to determine ascending numerical order,
- * this method uses the total order imposed by {@link Float#compareTo}.
- * This ordering differs from the {@code <} relation in that {@code -0.0f}
- * is treated as less than {@code 0.0f} and NaN is considered greater than
- * any other floating-point value. For the purposes of sorting, all NaN
- * values are considered equivalent and equal.
- *
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
- * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
- * offers O(n log(n)) performance on many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
- * faster than traditional (one-pivot) Quicksort implementations.
- *
- * @param a the array to be sorted
- */
- public static void sort(float[] a) {
- sort(a, 0, a.length);
+ DualPivotQuicksort.sort(a, fromIndex, toIndex);
}
- /**
- * Sorts the specified range of the specified array into ascending order. The
- * range of to be sorted extends from the index {@code fromIndex}, inclusive,
- * to the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
- * the range to be sorted is empty.
+ /*
+ * Sorting of complex type arrays.
*
- * <p>The {@code <} relation does not provide a total order on
- * all floating-point values; although they are distinct numbers
- * {@code -0.0f == 0.0f} is {@code true} and a NaN value compares
- * neither less than, greater than, nor equal to any floating-point
- * value, even itself. To allow the sort to proceed, instead of using
- * the {@code <} relation to determine ascending numerical order,
- * this method uses the total order imposed by {@link Float#compareTo}.
- * This ordering differs from the {@code <} relation in that {@code -0.0f}
- * is treated as less than {@code 0.0f} and NaN is considered greater than
- * any other floating-point value. For the purposes of sorting, all NaN
- * values are considered equivalent and equal.
- *
- * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort,
- * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
- * offers O(n log(n)) performance on many data sets that cause other
- * quicksorts to degrade to quadratic performance, and is typically
- * faster than traditional (one-pivot) Quicksort implementations.
- *
- * @param a the array to be sorted
- * @param fromIndex the index of the first element, inclusively, to be sorted
- * @param toIndex the index of the last element, exclusively, to be sorted
- * @throws IllegalArgumentException if {@code fromIndex > toIndex}
- * @throws ArrayIndexOutOfBoundsException
- * if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
- public static void sort(float[] a, int fromIndex, int toIndex) {
- rangeCheck(a.length, fromIndex, toIndex);
- sortNegZeroAndNaN(a, fromIndex, toIndex);
- }
-
- private static void sortNegZeroAndNaN(float[] a, int fromIndex, int toIndex) {
- final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
- /*
- * The sort is done in three phases to avoid the expense of using
- * NaN and -0.0f aware comparisons during the main sort.
- *
- * Preprocessing phase: move any NaN's to end of array, count the
- * number of -0.0f's, and turn them into 0.0f's.
- */
- int numNegZeros = 0;
- int i = fromIndex;
- int n = toIndex;
- float temp;
-
- while (i < n) {
- if (a[i] != a[i]) {
- n--;
- temp = a[i];
- a[i] = a[n];
- a[n] = temp;
- }
- else {
- if (a[i] == 0 && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) {
- a[i] = 0.0f;
- numNegZeros++;
- }
- i++;
- }
- }
- // Main sort phase: quicksort everything but the NaN's
- DualPivotQuicksort.sort(a, fromIndex, n - 1);
-
- // Postprocessing phase: change 0.0f's to -0.0f's as required
- if (numNegZeros != 0) {
- int j = binarySearch0(a, fromIndex, n, 0.0f); // position of ANY zero
-
- do {
- j--;
- }
- while (j >= fromIndex && a[j] == 0.0f);
-
- // j is now one less than the index of the FIRST zero
- for (int k = 0; k < numNegZeros; k++) {
- a[++j] = -0.0f;
- }
- }
- }
/**
* Old merge sort implementation can be selected (for
--- a/jdk/src/share/classes/java/util/DualPivotQuicksort.java Tue Nov 10 13:09:50 2009 +0000
+++ b/jdk/src/share/classes/java/util/DualPivotQuicksort.java Wed Nov 11 14:38:01 2009 +0000
@@ -36,11 +36,11 @@
* @author Jon Bentley
* @author Josh Bloch
*
- * @version 2009.10.29 m765.827.v5
+ * @version 2009.11.09 m765.827.v8
*/
final class DualPivotQuicksort {
- // Suppresses default constructor, ensuring non-instantiability.
+ // Suppresses default constructor
private DualPivotQuicksort() {}
/*
@@ -70,13 +70,43 @@
*/
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(int[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
- static void sort(int[] a, int left, int right) {
+ public static void sort(int[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(int[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -94,12 +124,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(int[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -234,8 +264,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -271,17 +301,47 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(long[] a) {
+ doSort(a, 0, a.length - 1);
}
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
- static void sort(long[] a, int left, int right) {
+ public static void sort(long[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(long[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -299,12 +359,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(long[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -439,8 +499,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -476,20 +536,50 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(short[] a) {
+ doSort(a, 0, a.length - 1);
}
- /** The number of distinct short values */
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(short[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /** The number of distinct short values. */
private static final int NUM_SHORT_VALUES = 1 << 16;
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
- static void sort(short[] a, int left, int right) {
+ private static void doSort(short[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -501,7 +591,7 @@
}
a[j + 1] = ak;
}
- } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
// Use counting sort on huge arrays
int[] count = new int[NUM_SHORT_VALUES];
@@ -521,12 +611,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(short[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -661,8 +751,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -698,242 +788,50 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
}
- /** The number of distinct byte values */
- private static final int NUM_BYTE_VALUES = 1 << 8;
-
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified array into ascending numerical order.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
*/
- static void sort(byte[] a, int left, int right) {
- // Use insertion sort on tiny arrays
- if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
- for (int k = left + 1; k <= right; k++) {
- byte ak = a[k];
- int j;
-
- for (j = k - 1; j >= left && ak < a[j]; j--) {
- a[j + 1] = a[j];
- }
- a[j + 1] = ak;
- }
- } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
- // Use counting sort on huge arrays
- int[] count = new int[NUM_BYTE_VALUES];
-
- for (int i = left; i <= right; i++) {
- count[a[i] - Byte.MIN_VALUE]++;
- }
- for (int i = 0, k = left; i < count.length && k <= right; i++) {
- byte value = (byte) (i + Byte.MIN_VALUE);
-
- for (int s = count[i]; s > 0; s--) {
- a[k++] = value;
- }
- }
- } else { // Use Dual-Pivot Quicksort on large arrays
- dualPivotQuicksort(a, left, right);
- }
+ public static void sort(char[] a) {
+ doSort(a, 0, a.length - 1);
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
*/
- private static void dualPivotQuicksort(byte[] a, int left, int right) {
- // Compute indices of five evenly spaced elements
- int sixth = (right - left + 1) / 6;
- int e1 = left + sixth;
- int e5 = right - sixth;
- int e3 = (left + right) >>> 1; // The midpoint
- int e4 = e3 + sixth;
- int e2 = e3 - sixth;
-
- // Sort these elements in place using a 5-element sorting network
- if (a[e1] > a[e2]) { byte t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
- if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
- if (a[e1] > a[e3]) { byte t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
- if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
- if (a[e1] > a[e4]) { byte t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
- if (a[e3] > a[e4]) { byte t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
- if (a[e2] > a[e5]) { byte t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
- if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
- if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
-
- /*
- * Use the second and fourth of the five sorted elements as pivots.
- * These values are inexpensive approximations of the first and
- * second terciles of the array. Note that pivot1 <= pivot2.
- *
- * The pivots are stored in local variables, and the first and
- * the last of the sorted elements are moved to the locations
- * formerly occupied by the pivots. When partitioning is complete,
- * the pivots are swapped back into their final positions, and
- * excluded from subsequent sorting.
- */
- byte pivot1 = a[e2]; a[e2] = a[left];
- byte pivot2 = a[e4]; a[e4] = a[right];
-
- /*
- * Partitioning
- *
- * left part center part right part
- * ------------------------------------------------------------
- * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
- * ------------------------------------------------------------
- * ^ ^ ^
- * | | |
- * less k great
- */
-
- // Pointers
- int less = left + 1; // The index of first element of center part
- int great = right - 1; // The index before first element of right part
-
- boolean pivotsDiffer = pivot1 != pivot2;
-
- if (pivotsDiffer) {
- /*
- * Invariants:
- * all in (left, less) < pivot1
- * pivot1 <= all in [less, k) <= pivot2
- * all in (great, right) > pivot2
- *
- * Pointer k is the first index of ?-part
- */
- for (int k = less; k <= great; k++) {
- byte ak = a[k];
-
- if (ak < pivot1) {
- a[k] = a[less];
- a[less++] = ak;
- } else if (ak > pivot2) {
- while (a[great] > pivot2 && k < great) {
- great--;
- }
- a[k] = a[great];
- a[great--] = ak;
- ak = a[k];
-
- if (ak < pivot1) {
- a[k] = a[less];
- a[less++] = ak;
- }
- }
- }
- } else { // Pivots are equal
- /*
- * Partition degenerates to the traditional 3-way
- * (or "Dutch National Flag") partition:
- *
- * left part center part right part
- * -------------------------------------------------
- * [ < pivot | == pivot | ? | > pivot ]
- * -------------------------------------------------
- *
- * ^ ^ ^
- * | | |
- * less k great
- *
- * Invariants:
- *
- * all in (left, less) < pivot
- * all in [less, k) == pivot
- * all in (great, right) > pivot
- *
- * Pointer k is the first index of ?-part
- */
- for (int k = less; k <= great; k++) {
- byte ak = a[k];
-
- if (ak == pivot1) {
- continue;
- }
- if (ak < pivot1) {
- a[k] = a[less];
- a[less++] = ak;
- } else {
- while (a[great] > pivot1) {
- great--;
- }
- a[k] = a[great];
- a[great--] = ak;
- ak = a[k];
-
- if (ak < pivot1) {
- a[k] = a[less];
- a[less++] = ak;
- }
- }
- }
- }
-
- // Swap pivots into their final positions
- a[left] = a[less - 1]; a[less - 1] = pivot1;
- a[right] = a[great + 1]; a[great + 1] = pivot2;
-
- // Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
-
- /*
- * If pivot1 == pivot2, all elements from center
- * part are equal and, therefore, already sorted
- */
- if (!pivotsDiffer) {
- return;
- }
-
- /*
- * If center part is too large (comprises > 5/6 of
- * the array), swap internal pivot values to ends
- */
- if (less < e1 && e5 < great) {
- while (a[less] == pivot1) {
- less++;
- }
- for (int k = less + 1; k <= great; k++) {
- if (a[k] == pivot1) {
- a[k] = a[less];
- a[less++] = pivot1;
- }
- }
- while (a[great] == pivot2) {
- great--;
- }
- for (int k = great - 1; k >= less; k--) {
- if (a[k] == pivot2) {
- a[k] = a[great];
- a[great--] = pivot2;
- }
- }
- }
-
- // Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ public static void sort(char[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
}
- /** The number of distinct char values */
+ /** The number of distinct char values. */
private static final int NUM_CHAR_VALUES = 1 << 16;
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
- static void sort(char[] a, int left, int right) {
+ private static void doSort(char[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -945,7 +843,7 @@
}
a[j + 1] = ak;
}
- } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
// Use counting sort on huge arrays
int[] count = new int[NUM_CHAR_VALUES];
@@ -963,12 +861,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(char[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -1103,8 +1001,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -1140,17 +1038,395 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(byte[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(byte[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /** The number of distinct byte values. */
+ private static final int NUM_BYTE_VALUES = 1 << 8;
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(byte[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ byte ak = a[k];
+ int j;
+
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+ // Use counting sort on huge arrays
+ int[] count = new int[NUM_BYTE_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i] - Byte.MIN_VALUE]++;
+ }
+ for (int i = 0, k = left; i < count.length && k <= right; i++) {
+ byte value = (byte) (i + Byte.MIN_VALUE);
+
+ for (int s = count[i]; s > 0; s--) {
+ a[k++] = value;
+ }
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
}
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
- static void sort(float[] a, int left, int right) {
+ private static void dualPivotQuicksort(byte[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements in place using a 5-element sorting network
+ if (a[e1] > a[e2]) { byte t = a[e1]; a[e1] = a[e2]; a[e2] = t; }
+ if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
+ if (a[e1] > a[e3]) { byte t = a[e1]; a[e1] = a[e3]; a[e3] = t; }
+ if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
+ if (a[e1] > a[e4]) { byte t = a[e1]; a[e1] = a[e4]; a[e4] = t; }
+ if (a[e3] > a[e4]) { byte t = a[e3]; a[e3] = a[e4]; a[e4] = t; }
+ if (a[e2] > a[e5]) { byte t = a[e2]; a[e2] = a[e5]; a[e5] = t; }
+ if (a[e2] > a[e3]) { byte t = a[e2]; a[e2] = a[e3]; a[e3] = t; }
+ if (a[e4] > a[e5]) { byte t = a[e4]; a[e4] = a[e5]; a[e5] = t; }
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ byte pivot1 = a[e2]; a[e2] = a[left];
+ byte pivot2 = a[e4]; a[e4] = a[right];
+
+ /*
+ * Partitioning
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ */
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Invariants:
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+
+ if (ak < pivot1) {
+ a[k] = a[less];
+ a[less++] = ak;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2 && k < great) {
+ great--;
+ }
+ a[k] = a[great];
+ a[great--] = ak;
+ ak = a[k];
+
+ if (ak < pivot1) {
+ a[k] = a[less];
+ a[less++] = ak;
+ }
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ *
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ a[k] = a[less];
+ a[less++] = ak;
+ } else {
+ while (a[great] > pivot1) {
+ great--;
+ }
+ a[k] = a[great];
+ a[great--] = ak;
+ ak = a[k];
+
+ if (ak < pivot1) {
+ a[k] = a[less];
+ a[less++] = ak;
+ }
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 5/6 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ for (int k = less + 1; k <= great; k++) {
+ if (a[k] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+ for (int k = great - 1; k >= less; k--) {
+ if (a[k] == pivot2) {
+ a[k] = a[great];
+ a[great--] = pivot2;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(float[] a) {
+ sortNegZeroAndNaN(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(float[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The
+ * sort is done in three phases to avoid expensive comparisons in the
+ * inner loop. The comparisons would be expensive due to anomalies
+ * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void sortNegZeroAndNaN(float[] a, int left, int right) {
+ /*
+ * Phase 1: Count negative zeros and move NaNs to end of array
+ */
+ final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+ int numNegativeZeros = 0;
+ int n = right;
+
+ for (int k = left; k <= n; k++) {
+ float ak = a[k];
+
+ if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
+ a[k] = 0.0f;
+ numNegativeZeros++;
+ } else if (ak != ak) { // i.e., ak is NaN
+ a[k--] = a[n];
+ a[n--] = Float.NaN;
+ }
+ }
+
+ /*
+ * Phase 2: Sort everything except NaNs (which are already in place)
+ */
+ doSort(a, left, n);
+
+ /*
+ * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ */
+ if (numNegativeZeros == 0) {
+ return;
+ }
+
+ // Find first zero element
+ int zeroIndex = findAnyZero(a, left, n);
+
+ for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
+ zeroIndex = i;
+ }
+
+ // Turn the right number of positive zeros back into negative zeros
+ for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+ a[i] = -0.0f;
+ }
+ }
+
+ /**
+ * Returns the index of some zero element in the specified range via
+ * binary search. The range is assumed to be sorted, and must contain
+ * at least one zero.
+ *
+ * @param a the array to be searched
+ * @param low the index of the first element, inclusive, to be searched
+ * @param high the index of the last element, inclusive, to be searched
+ */
+ private static int findAnyZero(float[] a, int low, int high) {
+ while (true) {
+ int middle = (low + high) >>> 1;
+ float middleValue = a[middle];
+
+ if (middleValue < 0.0f) {
+ low = middle + 1;
+ } else if (middleValue > 0.0f) {
+ high = middle - 1;
+ } else { // middleValue == 0.0f
+ return middle;
+ }
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in three ways:
+ * {@code right} index is inclusive, it does no range checking on
+ * {@code left} or {@code right}, and it does not handle negative
+ * zeros or NaNs in the array.
+ *
+ * @param a the array to be sorted, which must not contain -0.0f or NaN
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(float[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -1168,12 +1444,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(float[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -1308,8 +1584,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -1345,17 +1621,143 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(double[] a) {
+ sortNegZeroAndNaN(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ * @param fromIndex the index of the first element, inclusive, to be sorted
+ * @param toIndex the index of the last element, exclusive, to be sorted
+ * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(double[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
}
/**
- * Sorts the specified range of the array into ascending order.
+ * Sorts the specified range of the array into ascending order. The
+ * sort is done in three phases to avoid expensive comparisons in the
+ * inner loop. The comparisons would be expensive due to anomalies
+ * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
- static void sort(double[] a, int left, int right) {
+ private static void sortNegZeroAndNaN(double[] a, int left, int right) {
+ /*
+ * Phase 1: Count negative zeros and move NaNs to end of array
+ */
+ final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+ int numNegativeZeros = 0;
+ int n = right;
+
+ for (int k = left; k <= n; k++) {
+ double ak = a[k];
+
+ if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
+ a[k] = 0.0d;
+ numNegativeZeros++;
+ } else if (ak != ak) { // i.e., ak is NaN
+ a[k--] = a[n];
+ a[n--] = Double.NaN;
+ }
+ }
+
+ /*
+ * Phase 2: Sort everything except NaNs (which are already in place)
+ */
+ doSort(a, left, n);
+
+ /*
+ * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ */
+ if (numNegativeZeros == 0) {
+ return;
+ }
+
+ // Find first zero element
+ int zeroIndex = findAnyZero(a, left, n);
+
+ for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
+ zeroIndex = i;
+ }
+
+ // Turn the right number of positive zeros back into negative zeros
+ for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+ a[i] = -0.0d;
+ }
+ }
+
+ /**
+ * Returns the index of some zero element in the specified range via
+ * binary search. The range is assumed to be sorted, and must contain
+ * at least one zero.
+ *
+ * @param a the array to be searched
+ * @param low the index of the first element, inclusive, to be searched
+ * @param high the index of the last element, inclusive, to be searched
+ */
+ private static int findAnyZero(double[] a, int low, int high) {
+ while (true) {
+ int middle = (low + high) >>> 1;
+ double middleValue = a[middle];
+
+ if (middleValue < 0.0d) {
+ low = middle + 1;
+ } else if (middleValue > 0.0d) {
+ high = middle - 1;
+ } else { // middleValue == 0.0d
+ return middle;
+ }
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in three ways:
+ * {@code right} index is inclusive, it does no range checking on
+ * {@code left} or {@code right}, and it does not handle negative
+ * zeros or NaNs in the array.
+ *
+ * @param a the array to be sorted, which must not contain -0.0d and NaN
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(double[] a, int left, int right) {
// Use insertion sort on tiny arrays
if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
for (int k = left + 1; k <= right; k++) {
@@ -1373,12 +1775,12 @@
}
/**
- * Sorts the specified range of the array into ascending order
- * by Dual-Pivot Quicksort.
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
*
* @param a the array to be sorted
- * @param left the index of the first element, inclusively, to be sorted
- * @param right the index of the last element, inclusively, to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
*/
private static void dualPivotQuicksort(double[] a, int left, int right) {
// Compute indices of five evenly spaced elements
@@ -1513,8 +1915,8 @@
a[right] = a[great + 1]; a[great + 1] = pivot2;
// Sort left and right parts recursively, excluding known pivot values
- sort(a, left, less - 2);
- sort(a, great + 2, right);
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
/*
* If pivot1 == pivot2, all elements from center
@@ -1550,6 +1952,23 @@
}
// Sort center part recursively, excluding known pivot values
- sort(a, less, great);
+ doSort(a, less, great);
+ }
+
+ /**
+ * Checks that {@code fromIndex} and {@code toIndex} are in
+ * the range and throws an appropriate exception, if they aren't.
+ */
+ private static void rangeCheck(int length, int fromIndex, int toIndex) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > length) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
}
}
--- a/jdk/test/java/util/Arrays/Sorting.java Tue Nov 10 13:09:50 2009 +0000
+++ b/jdk/test/java/util/Arrays/Sorting.java Wed Nov 11 14:38:01 2009 +0000
@@ -23,11 +23,14 @@
/*
* @test
- * @bug 6880672 6896573
+ * @bug 6880672 6896573 6899694
* @summary Exercise Arrays.sort
* @build Sorting
* @run main Sorting -shortrun
- * @author Vladimir Yaroslavskiy, Josh Bloch, Jon Bentley
+ *
+ * @author Vladimir Yaroslavskiy
+ * @author Jon Bentley
+ * @author Josh Bloch
*/
import java.util.Arrays;
@@ -35,59 +38,300 @@
import java.io.PrintStream;
public class Sorting {
- static final PrintStream out = System.out;
- static final PrintStream err = System.err;
+ private static final PrintStream out = System.out;
+ private static final PrintStream err = System.err;
+
+ // Array lengths used in a long run (default)
+ private static final int[] LONG_RUN_LENGTHS = {
+ 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};
- // array lengths used in a long run (default)
- static final int[] LONG_RUN = {
- 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};
+ // Array lengths used in a short run
+ private static final int[] SHORT_RUN_LENGTHS = { 1, 2, 3, 21, 55, 1000, 10000 };
- // array lengths used in a short run
- static final int[] SHORT_RUN = {0, 1, 2, 3, 21, 55, 1000, 10000, 500000};
+ // Random initial values used in a long run (default)
+ private static final long[] LONG_RUN_RANDOMS = {666, 0xC0FFEE, 999};
+
+ // Random initial values used in a short run
+ private static final long[] SHORT_RUN_RANDOMS = {666};
public static void main(String[] args) {
- boolean shortRun = false;
- if (args.length > 0 && args[0].equals("-shortrun"))
- shortRun = true;
+ boolean shortRun = args.length > 0 && args[0].equals("-shortrun");
+ long start = System.currentTimeMillis();
+
+ if (shortRun) {
+ testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);
+ } else {
+ testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);
+ }
+ long end = System.currentTimeMillis();
+
+ out.format("PASS in %d sec.\n", Math.round((end - start) / 1E3));
+ }
- long start = System.nanoTime();
+ private static void testAndCheck(int[] lengths, long[] randoms) {
+ for (long random : randoms) {
+ reset(random);
+
+ for (int len : lengths) {
+ testAndCheckWithCheckSum(len, random);
+ }
+ reset(random);
+
+ for (int len : lengths) {
+ testAndCheckWithScrambling(len, random);
+ }
+ reset(random);
+
+ for (int len : lengths) {
+ testAndCheckFloat(len, random);
+ }
+ reset(random);
- testAndCheck((shortRun) ? SHORT_RUN : LONG_RUN);
+ for (int len : lengths) {
+ testAndCheckDouble(len, random);
+ }
+ reset(random);
+
+ for (int len : lengths) {
+ testAndCheckRange(len, random);
+ }
+ reset(random);
+
+ for (int len : lengths) {
+ testAndCheckSubArray(len, random);
+ }
+ }
+ }
+
+ private static void testAndCheckSubArray(int len, long random) {
+ int[] golden = new int[len];
- long end = System.nanoTime();
+ for (int m = 1; m < len / 2; m *= 2) {
+ int fromIndex = m;
+ int toIndex = len - m;
+
+ prepareSubArray(golden, fromIndex, toIndex, m);
+ int[] test = golden.clone();
+ for (TypeConverter converter : TypeConverter.values()) {
+ out.println("Test #6: " + converter +
+ " len = " + len + ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ Object convertedTest = converter.convert(test);
+
+ // outArr(test);
+ sortSubArray(convertedTest, fromIndex, toIndex);
+ // outArr(test);
+ checkSubArray(convertedTest, fromIndex, toIndex, m);
+ }
+ }
out.println();
- out.format("PASS in %ds%n", Math.round((end - start) / 1e9));
}
- static void testAndCheck(int[] lengths) {
- for (int len : lengths) {
- out.println();
- ArrayBuilder.reset();
- int[] golden = new int[len];
+ private static void testAndCheckRange(int len, long random) {
+ int[] golden = new int[len];
+
+ for (int m = 1; m < 2 * len; m *= 2) {
+ for (int i = 1; i <= len; i++) {
+ golden[i - 1] = i % m + m % i;
+ }
+ for (TypeConverter converter : TypeConverter.values()) {
+ out.println("Test #5: " + converter +
+ ", len = " + len + ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ sortRange(convertedGolden, m);
+ sortEmpty(convertedGolden);
+ }
+ }
+ out.println();
+ }
+
+ private static void testAndCheckWithCheckSum(int len, long random) {
+ int[] golden = new int[len];
+
+ for (int m = 1; m < 2 * len; m *= 2) {
+ for (UnsortedBuilder builder : UnsortedBuilder.values()) {
+ builder.build(golden, m);
+ int[] test = golden.clone();
+
+ for (TypeConverter converter : TypeConverter.values()) {
+ out.println("Test #1: " + converter + " " + builder +
+ "random = " + random + ", len = " + len +
+ ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ Object convertedTest = converter.convert(test);
+ sort(convertedTest);
+ checkWithCheckSum(convertedTest, convertedGolden);
+ }
+ }
+ }
+ out.println();
+ }
+
+ private static void testAndCheckWithScrambling(int len, long random) {
+ int[] golden = new int[len];
- for (int m = 1; m < 2 * len; m *= 2) {
- for (ArrayBuilder builder : ArrayBuilder.values()) {
- builder.build(golden, m);
- int[] test = golden.clone();
+ for (int m = 1; m <= 7; m++) {
+ if (m > len) {
+ break;
+ }
+ for (SortedBuilder builder : SortedBuilder.values()) {
+ builder.build(golden, m);
+ int[] test = golden.clone();
+ scramble(test);
+
+ for (TypeConverter converter : TypeConverter.values()) {
+ out.println("Test #2: " + converter + " " + builder +
+ "random = " + random + ", len = " + len +
+ ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ Object convertedTest = converter.convert(test);
+ sort(convertedTest);
+ compare(convertedTest, convertedGolden);
+ }
+ }
+ }
+ out.println();
+ }
- for (Converter converter : Converter.values()) {
- out.println("Test: " + converter + " " + builder +
- "len = " + len + ", m = " + m);
- Object convertedGolden = converter.convert(golden);
- Object convertedTest = converter.convert(test);
- sort(convertedTest);
- checkWithCheckSum(convertedTest, convertedGolden);
+ private static void testAndCheckFloat(int len, long random) {
+ float[] golden = new float[len];
+ final int MAX = 10;
+ boolean newLine = false;
+
+ for (int a = 0; a <= MAX; a++) {
+ for (int g = 0; g <= MAX; g++) {
+ for (int z = 0; z <= MAX; z++) {
+ for (int n = 0; n <= MAX; n++) {
+ for (int p = 0; p <= MAX; p++) {
+ if (a + g + z + n + p > len) {
+ continue;
+ }
+ if (a + g + z + n + p < len) {
+ continue;
+ }
+ for (FloatBuilder builder : FloatBuilder.values()) {
+ out.println("Test #3: random = " + random +
+ ", len = " + len + ", a = " + a + ", g = " + g +
+ ", z = " + z + ", n = " + n + ", p = " + p);
+ builder.build(golden, a, g, z, n, p);
+ float[] test = golden.clone();
+ scramble(test);
+ // outArr(test);
+ sort(test);
+ // outArr(test);
+ compare(test, golden, a, n, g);
+ }
+ newLine = true;
+ }
}
}
}
}
+ if (newLine) {
+ out.println();
+ }
+ }
+
+ private static void testAndCheckDouble(int len, long random) {
+ double[] golden = new double[len];
+ final int MAX = 10;
+ boolean newLine = false;
+
+ for (int a = 0; a <= MAX; a++) {
+ for (int g = 0; g <= MAX; g++) {
+ for (int z = 0; z <= MAX; z++) {
+ for (int n = 0; n <= MAX; n++) {
+ for (int p = 0; p <= MAX; p++) {
+ if (a + g + z + n + p > len) {
+ continue;
+ }
+ if (a + g + z + n + p < len) {
+ continue;
+ }
+ for (DoubleBuilder builder : DoubleBuilder.values()) {
+ out.println("Test #4: random = " + random +
+ ", len = " + len + ", a = " + a + ", g = " + g +
+ ", z = " + z + ", n = " + n + ", p = " + p);
+ builder.build(golden, a, g, z, n, p);
+ double[] test = golden.clone();
+ scramble(test);
+ // outArr(test);
+ sort(test);
+ // outArr(test);
+ compare(test, golden, a, n, g);
+ }
+ newLine = true;
+ }
+ }
+ }
+ }
+ }
+ if (newLine) {
+ out.println();
+ }
}
- static enum Converter {
+ private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ a[i] = 0xBABA;
+ }
+
+ for (int i = fromIndex; i < toIndex; i++) {
+ a[i] = -i + m;
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ a[i] = 0xDEDA;
+ }
+ }
+
+ private static void scramble(int[] a) {
+ int length = a.length;
+
+ for (int i = 0; i < length * 7; i++) {
+ swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+ }
+ }
+
+ private static void scramble(float[] a) {
+ int length = a.length;
+
+ for (int i = 0; i < length * 7; i++) {
+ swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+ }
+ }
+
+ private static void scramble(double[] a) {
+ int length = a.length;
+
+ for (int i = 0; i < length * 7; i++) {
+ swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));
+ }
+ }
+
+ private static void swap(int[] a, int i, int j) {
+ int t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+
+ private static void swap(float[] a, int i, int j) {
+ float t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+
+ private static void swap(double[] a, int i, int j) {
+ double t = a[i];
+ a[i] = a[j];
+ a[j] = t;
+ }
+
+ private static enum TypeConverter {
INT {
Object convert(int[] a) {
- return a;
+ return a.clone();
}
},
LONG {
@@ -95,7 +339,7 @@
long[] b = new long[a.length];
for (int i = 0; i < a.length; i++) {
- b[i] = (int) a[i];
+ b[i] = (long) a[i];
}
return b;
}
@@ -163,7 +407,161 @@
}
}
- static enum ArrayBuilder {
+ private static enum FloatBuilder {
+ SIMPLE {
+ void build(float[] x, int a, int g, int z, int n, int p) {
+ int fromIndex = 0;
+ float negativeValue = -ourRandom.nextFloat();
+ float positiveValue = ourRandom.nextFloat();
+
+ writeValue(x, negativeValue, fromIndex, n);
+ fromIndex += n;
+
+ writeValue(x, -0.0f, fromIndex, g);
+ fromIndex += g;
+
+ writeValue(x, 0.0f, fromIndex, z);
+ fromIndex += z;
+
+ writeValue(x, positiveValue, fromIndex, p);
+ fromIndex += p;
+
+ writeValue(x, Float.NaN, fromIndex, a);
+ }
+ };
+
+ abstract void build(float[] x, int a, int g, int z, int n, int p);
+ }
+
+ private static enum DoubleBuilder {
+ SIMPLE {
+ void build(double[] x, int a, int g, int z, int n, int p) {
+ int fromIndex = 0;
+ double negativeValue = -ourRandom.nextFloat();
+ double positiveValue = ourRandom.nextFloat();
+
+ writeValue(x, negativeValue, fromIndex, n);
+ fromIndex += n;
+
+ writeValue(x, -0.0d, fromIndex, g);
+ fromIndex += g;
+
+ writeValue(x, 0.0d, fromIndex, z);
+ fromIndex += z;
+
+ writeValue(x, positiveValue, fromIndex, p);
+ fromIndex += p;
+
+ writeValue(x, Double.NaN, fromIndex, a);
+ }
+ };
+
+ abstract void build(double[] x, int a, int g, int z, int n, int p);
+ }
+
+ private static void writeValue(float[] a, float value, int fromIndex, int count) {
+ for (int i = fromIndex; i < fromIndex + count; i++) {
+ a[i] = value;
+ }
+ }
+
+ private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {
+ for (int i = a.length - numNaN; i < a.length; i++) {
+ if (a[i] == a[i]) {
+ failed("On position " + i + " must be NaN instead of " + a[i]);
+ }
+ }
+ final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+
+ for (int i = numNeg; i < numNeg + numNegZero; i++) {
+ if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {
+ failed("On position " + i + " must be -0.0f instead of " + a[i]);
+ }
+ }
+ for (int i = 0; i < a.length - numNaN; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static void writeValue(double[] a, double value, int fromIndex, int count) {
+ for (int i = fromIndex; i < fromIndex + count; i++) {
+ a[i] = value;
+ }
+ }
+
+ private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {
+ for (int i = a.length - numNaN; i < a.length; i++) {
+ if (a[i] == a[i]) {
+ failed("On position " + i + " must be NaN instead of " + a[i]);
+ }
+ }
+ final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+
+ for (int i = numNeg; i < numNeg + numNegZero; i++) {
+ if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {
+ failed("On position " + i + " must be -0.0d instead of " + a[i]);
+ }
+ }
+ for (int i = 0; i < a.length - numNaN; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static enum SortedBuilder {
+ REPEATED {
+ void build(int[] a, int m) {
+ int period = a.length / m;
+ int i = 0;
+ int k = 0;
+
+ while (true) {
+ for (int t = 1; t <= period; t++) {
+ if (i >= a.length) {
+ return;
+ }
+ a[i++] = k;
+ }
+ if (i >= a.length) {
+ return;
+ }
+ k++;
+ }
+ }
+ },
+
+ ORGAN_PIPES {
+ void build(int[] a, int m) {
+ int i = 0;
+ int k = m;
+
+ while (true) {
+ for (int t = 1; t <= m; t++) {
+ if (i >= a.length) {
+ return;
+ }
+ a[i++] = k;
+ }
+ }
+ }
+ };
+
+ abstract void build(int[] a, int m);
+
+ @Override public String toString() {
+ String name = name();
+
+ for (int i = name.length(); i < 12; i++) {
+ name += " ";
+ }
+ return name;
+ }
+ }
+
+ private static enum UnsortedBuilder {
RANDOM {
void build(int[] a, int m) {
for (int i = 0; i < a.length; i++) {
@@ -268,41 +666,53 @@
abstract void build(int[] a, int m);
- static void reset() {
- ourRandom = new Random(666);
- ourFirst = 0;
- ourSecond = 0;
- }
-
@Override public String toString() {
String name = name();
+
for (int i = name.length(); i < 12; i++) {
name += " ";
}
return name;
}
-
- private static int ourFirst;
- private static int ourSecond;
- private static Random ourRandom = new Random(666);
}
- static void checkWithCheckSum(Object test, Object golden) {
+ private static void compare(Object test, Object golden) {
+ if (test instanceof int[]) {
+ compare((int[]) test, (int[]) golden);
+ } else if (test instanceof long[]) {
+ compare((long[]) test, (long[]) golden);
+ } else if (test instanceof short[]) {
+ compare((short[]) test, (short[]) golden);
+ } else if (test instanceof byte[]) {
+ compare((byte[]) test, (byte[]) golden);
+ } else if (test instanceof char[]) {
+ compare((char[]) test, (char[]) golden);
+ } else if (test instanceof float[]) {
+ compare((float[]) test, (float[]) golden);
+ } else if (test instanceof double[]) {
+ compare((double[]) test, (double[]) golden);
+ } else {
+ failed("Unknow type of array: " + test + " of class " +
+ test.getClass().getName());
+ }
+ }
+
+ private static void checkWithCheckSum(Object test, Object golden) {
checkSorted(test);
checkCheckSum(test, golden);
}
- static void failed(String message) {
- err.format("***FAILED: %s%%n", message);
+ private static void failed(String message) {
+ err.format("\n*** FAILED: %s\n\n", message);
throw new RuntimeException("Test failed - see log file for details");
}
- static void failed(int index, String value1, String value2) {
+ private static void failed(int index, String value1, String value2) {
failed("Array is not sorted at " + index + "-th position: " + value1 +
" and " + value2);
}
- static void checkSorted(Object object) {
+ private static void checkSorted(Object object) {
if (object instanceof int[]) {
checkSorted((int[]) object);
} else if (object instanceof long[]) {
@@ -323,31 +733,63 @@
}
}
- static void checkSorted(int[] a) {
- for (int i = 0; i < a.length - 1; i++) {
- if (a[i] > a[i + 1]) {
- failed(i, "" + a[i], "" + a[i + 1]);
+ private static void compare(int[] a, int[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static void compare(long[] a, long[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static void compare(short[] a, short[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
}
}
}
- static void checkSorted(long[] a) {
- for (int i = 0; i < a.length - 1; i++) {
- if (a[i] > a[i + 1]) {
- failed(i, "" + a[i], "" + a[i + 1]);
+ private static void compare(byte[] a, byte[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static void compare(char[] a, char[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
}
}
}
- static void checkSorted(short[] a) {
- for (int i = 0; i < a.length - 1; i++) {
- if (a[i] > a[i + 1]) {
- failed(i, "" + a[i], "" + a[i + 1]);
+ private static void compare(float[] a, float[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
}
}
}
- static void checkSorted(byte[] a) {
+ private static void compare(double[] a, double[] b) {
+ for (int i = 0; i < a.length; i++) {
+ if (a[i] != b[i]) {
+ failed(i, "" + a[i], "" + b[i]);
+ }
+ }
+ }
+
+ private static void checkSorted(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failed(i, "" + a[i], "" + a[i + 1]);
@@ -355,7 +797,7 @@
}
}
- static void checkSorted(char[] a) {
+ private static void checkSorted(long[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failed(i, "" + a[i], "" + a[i + 1]);
@@ -363,7 +805,15 @@
}
}
- static void checkSorted(float[] a) {
+ private static void checkSorted(short[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private static void checkSorted(byte[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failed(i, "" + a[i], "" + a[i + 1]);
@@ -371,7 +821,15 @@
}
}
- static void checkSorted(double[] a) {
+ private static void checkSorted(char[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private static void checkSorted(float[] a) {
for (int i = 0; i < a.length - 1; i++) {
if (a[i] > a[i + 1]) {
failed(i, "" + a[i], "" + a[i + 1]);
@@ -379,13 +837,21 @@
}
}
- static void checkCheckSum(Object test, Object golden) {
+ private static void checkSorted(double[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private static void checkCheckSum(Object test, Object golden) {
if (checkSum(test) != checkSum(golden)) {
failed("Original and sorted arrays seems not identical");
}
}
- static int checkSum(Object object) {
+ private static int checkSum(Object object) {
if (object instanceof int[]) {
return checkSum((int[]) object);
} else if (object instanceof long[]) {
@@ -407,70 +873,70 @@
}
}
- static int checkSum(int[] a) {
- int checkSum = 0;
+ private static int checkSum(int[] a) {
+ int checkXorSum = 0;
for (int e : a) {
- checkSum ^= e; // xor
+ checkXorSum ^= e;
}
- return checkSum;
+ return checkXorSum;
}
- static int checkSum(long[] a) {
- long checkSum = 0;
+ private static int checkSum(long[] a) {
+ long checkXorSum = 0;
for (long e : a) {
- checkSum ^= e; // xor
+ checkXorSum ^= e;
}
- return (int) checkSum;
+ return (int) checkXorSum;
}
- static int checkSum(short[] a) {
- short checkSum = 0;
+ private static int checkSum(short[] a) {
+ short checkXorSum = 0;
for (short e : a) {
- checkSum ^= e; // xor
+ checkXorSum ^= e;
}
- return (int) checkSum;
+ return (int) checkXorSum;
}
- static int checkSum(byte[] a) {
- byte checkSum = 0;
+ private static int checkSum(byte[] a) {
+ byte checkXorSum = 0;
for (byte e : a) {
- checkSum ^= e; // xor
+ checkXorSum ^= e;
}
- return (int) checkSum;
+ return (int) checkXorSum;
}
- static int checkSum(char[] a) {
- char checkSum = 0;
+ private static int checkSum(char[] a) {
+ char checkXorSum = 0;
for (char e : a) {
- checkSum ^= e; // xor
+ checkXorSum ^= e;
}
- return (int) checkSum;
+ return (int) checkXorSum;
}
- static int checkSum(float[] a) {
- int checkSum = 0;
+ private static int checkSum(float[] a) {
+ int checkXorSum = 0;
for (float e : a) {
- checkSum ^= (int) e; // xor
+ checkXorSum ^= (int) e;
}
- return checkSum;
+ return checkXorSum;
}
- static int checkSum(double[] a) {
- int checkSum = 0;
+ private static int checkSum(double[] a) {
+ int checkXorSum = 0;
for (double e : a) {
- checkSum ^= (int) e; // xor
+ checkXorSum ^= (int) e;
}
- return checkSum;
+ return checkXorSum;
}
- static void sort(Object object) {
+ private static void sort(Object object) {
if (object instanceof int[]) {
Arrays.sort((int[]) object);
} else if (object instanceof long[]) {
@@ -490,4 +956,485 @@
object.getClass().getName());
}
}
+
+ private static void sortSubArray(Object object, int fromIndex, int toIndex) {
+ if (object instanceof int[]) {
+ Arrays.sort((int[]) object, fromIndex, toIndex);
+ } else if (object instanceof long[]) {
+ Arrays.sort((long[]) object, fromIndex, toIndex);
+ } else if (object instanceof short[]) {
+ Arrays.sort((short[]) object, fromIndex, toIndex);
+ } else if (object instanceof byte[]) {
+ Arrays.sort((byte[]) object, fromIndex, toIndex);
+ } else if (object instanceof char[]) {
+ Arrays.sort((char[]) object, fromIndex, toIndex);
+ } else if (object instanceof float[]) {
+ Arrays.sort((float[]) object, fromIndex, toIndex);
+ } else if (object instanceof double[]) {
+ Arrays.sort((double[]) object, fromIndex, toIndex);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+
+ private static void checkSubArray(Object object, int fromIndex, int toIndex, int m) {
+ if (object instanceof int[]) {
+ checkSubArray((int[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof long[]) {
+ checkSubArray((long[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof short[]) {
+ checkSubArray((short[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof byte[]) {
+ checkSubArray((byte[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof char[]) {
+ checkSubArray((char[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof float[]) {
+ checkSubArray((float[]) object, fromIndex, toIndex, m);
+ } else if (object instanceof double[]) {
+ checkSubArray((double[]) object, fromIndex, toIndex, m);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+
+ private static void checkSubArray(int[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(byte[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (byte) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (byte) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(long[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (long) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (long) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(char[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (char) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (char) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(short[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (short) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (short) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(float[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (float) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (float) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void checkSubArray(double[] a, int fromIndex, int toIndex, int m) {
+ for (int i = 0; i < fromIndex; i++) {
+ if (a[i] != (double) 0xBABA) {
+ failed("Range sort changes left element on position " + i +
+ ": " + a[i] + ", must be " + 0xBABA);
+ }
+ }
+
+ for (int i = fromIndex; i < toIndex - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+
+ for (int i = toIndex; i < a.length; i++) {
+ if (a[i] != (double) 0xDEDA) {
+ failed("Range sort changes right element on position " + i +
+ ": " + a[i] + ", must be " + 0xDEDA);
+ }
+ }
+ }
+
+ private static void sortRange(Object object, int m) {
+ if (object instanceof int[]) {
+ sortRange((int[]) object, m);
+ } else if (object instanceof long[]) {
+ sortRange((long[]) object, m);
+ } else if (object instanceof short[]) {
+ sortRange((short[]) object, m);
+ } else if (object instanceof byte[]) {
+ sortRange((byte[]) object, m);
+ } else if (object instanceof char[]) {
+ sortRange((char[]) object, m);
+ } else if (object instanceof float[]) {
+ sortRange((float[]) object, m);
+ } else if (object instanceof double[]) {
+ sortRange((double[]) object, m);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+
+ private static void sortEmpty(Object object) {
+ if (object instanceof int[]) {
+ Arrays.sort(new int [] {});
+ } else if (object instanceof long[]) {
+ Arrays.sort(new long [] {});
+ } else if (object instanceof short[]) {
+ Arrays.sort(new short [] {});
+ } else if (object instanceof byte[]) {
+ Arrays.sort(new byte [] {});
+ } else if (object instanceof char[]) {
+ Arrays.sort(new char [] {});
+ } else if (object instanceof float[]) {
+ Arrays.sort(new float [] {});
+ } else if (object instanceof double[]) {
+ Arrays.sort(new double [] {});
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+
+ private static void sortRange(int[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(long[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(byte[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(short[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(char[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(float[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void sortRange(double[] a, int m) {
+ try {
+ Arrays.sort(a, m + 1, m);
+
+ failed("Sort does not throw IllegalArgumentException " +
+ " as expected: fromIndex = " + (m + 1) +
+ " toIndex = " + m);
+ }
+ catch (IllegalArgumentException iae) {
+ try {
+ Arrays.sort(a, -m, a.length);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: fromIndex = " + (-m));
+ }
+ catch (ArrayIndexOutOfBoundsException aoe) {
+ try {
+ Arrays.sort(a, 0, a.length + m);
+
+ failed("Sort does not throw ArrayIndexOutOfBoundsException " +
+ " as expected: toIndex = " + (a.length + m));
+ }
+ catch (ArrayIndexOutOfBoundsException aie) {
+ return;
+ }
+ }
+ }
+ }
+
+ private static void prepareRandom(int[] a) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = ourRandom.nextInt();
+ }
+ }
+
+ private static void reset(long seed) {
+ ourRandom = new Random(seed);
+ ourFirst = 0;
+ ourSecond = 0;
+ }
+
+ private static void outArr(int[] a) {
+ for (int i = 0; i < a.length; i++) {
+ out.print(a[i] + " ");
+ }
+ out.println();
+ out.println();
+ }
+
+ private static void outArr(float[] a) {
+ for (int i = 0; i < a.length; i++) {
+ out.print(a[i] + " ");
+ }
+ out.println();
+ out.println();
+ }
+
+ private static void outArr(double[] a) {
+ for (int i = 0; i < a.length; i++) {
+ out.print(a[i] + " ");
+ }
+ out.println();
+ out.println();
+ }
+
+ private static int ourFirst;
+ private static int ourSecond;
+ private static Random ourRandom;
}