import java.util.*;
class IntegerComparator implements Comparator<Integer> {
public int cmpCount = 0;
public int compare(Integer a, Integer b) {
++cmpCount;
return a - b;
}
}
public class MySorters {
/* Private Values */
private static boolean tryToReduceSwaps = true;
private static boolean useMiddleAsPivot = true;
private static boolean compoundPivot = true;
private static int swapCount = 0;
private static int cmp2Count = 0;
private static IntegerComparator comparator = new IntegerComparator();
/* Quicksort Method */
public static void quicksort(Integer[] array, int lower, int upper) {
if (upper - lower < 2) return;
int[] p = partition(array, lower, upper);
quicksort(array, lower, p[0]);
quicksort(array, p[1] + 1, upper);
}
/* Quicksort Functions */
private static int[] partition(Integer[] array, int lower, int upper) {
// Variable Declarations
int iVal, jVal; // Values at indices i and j.
int cmpVal; // The result of a comparison.
boolean equalsPivot, needsToMove;
int[] p = new int[2]; // Array of left and right pivot boundaries.
// Pivot Initialization
int pivotIndex = getPivotIndex(array, lower, upper);
p[0] = pivotIndex; // An index defining the pivot's left boundary.
p[1] = pivotIndex; // An index defining the pivot's right boundary.
final int pVal = array[pivotIndex]; // The pivot value.
// We begin with values of i and j that are indices immediately to the
// left of and to the right of the pivot index respectively. From there
// we decrement i (moving i toward lower), and we increment j (moving j
// toward upper).
//
// Note: We cannot begin with i equal to lower and j equal to upper (or
// upper - 1) and move i and j toward the pivot. Why not? Exercise: Try
// it, and find a sequence to sort that exposes the problem.
int i = pivotIndex - 1, j = pivotIndex + 1;
// For each iteration of the following optional while loop, we will
// exchange a value at position i that is greater than the pivot value
// with a value at position j that is less than the pivot value, or we
// will break out of the loop, either because the value of i is les
// than lower or because the value of j is equal to upper.
while (tryToReduceSwaps) {
// The following while loop has the effect of decrementing i until
// it is either the index of a value that is greater than the pivot
// value or it is less than lower. In the process, any values
// (corresponding to the current value of i) that are equal to the
// pivot value are merged with the pivot if the value of
// compoundPivot is true.
while (ge2(i, lower) && le1(iVal = array[i], pVal)) {
// If the value at index i is equal to the pivot value and
// the pivot can span more than one element in the array
// (i.e. compoundPivot is true), then merge the value at
// index i with the pivot.
if (compoundPivot && eq1(iVal, pVal)) {
// If the value at index i is not immediately to the left
// of the pivot, then move it there, by swapping it with
// the value that is to the left of the pivot.
if (ne2(i, p[0] - 1)) {
swap(array, i, p[0] - 1);
}
--p[0]; // Decrease the pivot's left boundary.
}
--i;
}
// The following while loop has the effect of incrementing j until
// it is either the index of a value that is less than the pivot
// value or it is equal to upper. In the process, any values
// (corresponding to the current value of j) that are equal to the
// pivot value are merged with the pivot if the value of
// compoundPivot is true.
while (lt2(j, upper) && ge1(jVal = array[j], pVal)) {
// If the value at index j is equal to the pivot value and
// the pivot can span more than one element in the array
// (i.e. compoundPivot is true), then merge the value at
// index j with the pivot.
if (compoundPivot && eq1(jVal, pVal)) {
// If the value at index j is not immediately to the right
// of the pivot, then move it there, by swapping it with
// the value that is to the right of the pivot.
if (ne2(j, p[1] + 1)) {
swap(array, j, p[1] + 1);
}
++p[1]; // Increase the pivot's right boundary.
}
++j;
}
// If the value of i is less than lower or the value of j equals
// upper, then there are no more pairs of elements to the left of
// and to the right of the pivot that need to be moved and can
// therefore be swapped; hence, we break out of the outer while
// loop and proceed to the next part of the partitioning algorithm.
if (lt2(i, lower) || eq2(j, upper)) {
break;
}
// Otherwise, the values of i and j identify values that need to be
// moved to opposite sides of the pivot, so we swap the two values.
// Then we decrement i, increment j, and repeat.
else {
swap(array, i, j);
--i;
++j;
}
}
// We (continue to) decrement i, moving the value of i toward lower until
// the value of i is less than lower. At that point, all the values that
// were originally to the left of the pivot when partition was involked
// and were greater than the pivot value will have been moved to the right
// of the pivot.
while (ge2(i, lower)) {
cmpVal = cmp1(array[i], pVal);
equalsPivot = cmpVal == 0;
needsToMove = cmpVal > 0;
// If the value at position i is equal to the pivot value and the pivot
// may contain multiple elements (compoundPivot is true), or if the
// value at position i is greater than the pivot value, then the value
// might need to be moved and at least one pivot boundary will need to
// be adjusted.
if ((compoundPivot && equalsPivot) || needsToMove) {
// If i is not the index of the element immediate to the left of
// the pivot, then we need to swap the value at that position with
// the value at index i.
if (ne2(i, p[0] - 1)) {
swap(array, i, p[0] - 1);
}
// If the value at index i needs to move to the other side of the
// pivot, then swap the value with the pivot's right boundary and
// decrement the right boundary.
if (needsToMove) {
swap(array, p[0] - 1, p[1]);
--p[1];
}
// Decrement the pivot's left boundary.
--p[0];
}
--i;
}
// We (continue to) increment j, moving the value of j toward upper until
// the value of j is equal to upper. At that point, all the values that
// were originally to the right of the pivot when partition was involked
// and were less than the pivot value will have been moved to the left
// of the pivot.
while (lt2(j, upper)) {
cmpVal = cmp1(array[j], pVal);
equalsPivot = cmpVal == 0;
needsToMove = cmpVal < 0;
// If the value at position j is equal to the pivot value and the pivot
// may contain multiple elements (compoundPivot is true), or if the
// value at position j is less than the pivot, then the value might need
// to be moved and at least one pivot boundary will need to be adjusted.
if ((compoundPivot && equalsPivot) || needsToMove) {
// If j is not the index of the element immediate to the right of
// the pivot, then we need to swap the value at that position with
// the value at index j.
if (ne2(j, p[1] + 1)) {
swap(array, p[1] + 1, j);
}
// If the value at index j needs to move to the other side of the
// pivot, then swap the value with the pivot's left boundary and
// increment the right boundary.
if (needsToMove) {
swap(array, p[1] + 1, p[0]);
++p[0];
}
// Increment the pivot's right boundary.
++p[1];
}
++j;
}
// Return the array of pivot boundaries.
return p;
}
private static int getPivotIndex(Integer[] array, int lower, int upper) {
return useMiddleAsPivot ? lower + ((upper - lower) / 2) : lower;
}
/* Compare Utilities */
private static int cmp1(int a, int b) {
return comparator.compare(a, b);
}
private static int cmp2(int a, int b) {
++cmp2Count;
return a - b;
}
private static boolean eq1(int a, int b) { return cmp1(a, b) == 0; }
private static boolean ne1(int a, int b) { return cmp1(a, b) != 0; }
private static boolean gt1(int a, int b) { return cmp1(a, b) > 0; }
private static boolean ge1(int a, int b) { return cmp1(a, b) >= 0; }
private static boolean lt1(int a, int b) { return cmp1(a, b) < 0; }
private static boolean le1(int a, int b) { return cmp1(a, b) <= 0; }
private static boolean eq2(int a, int b) { return cmp2(a, b) == 0; }
private static boolean ne2(int a, int b) { return cmp2(a, b) != 0; }
private static boolean gt2(int a, int b) { return cmp2(a, b) > 0; }
private static boolean ge2(int a, int b) { return cmp2(a, b) >= 0; }
private static boolean lt2(int a, int b) { return cmp2(a, b) < 0; }
private static boolean le2(int a, int b) { return cmp2(a, b) <= 0; }
/* Array Utilities and Functions */
private static void swap(Integer[] array, int i, int j) {
++swapCount;
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
private static Integer[] copy(Integer[] array) {
final int len = array.length;
Integer[] copyOfArray = new Integer[len];
for (int i = 0; i < len; i++) {
copyOfArray[i] = array[i];
}
return copyOfArray;
}
private static void printArray(Integer[] array) {
for (Integer i : array) {
System.out.print(i);
System.out.print(" ");
}
System.out.println();
}
private static void customSort(Integer[] array) {
resetStats();
System.out.println("\nQuicksort");
quicksort(array, 0, array.length);
printArray(array);
printStats();
}
private static void librarySort(Integer[] array) {
resetStats();
System.out.println("\nArrays.sort (Timsort)");
Arrays.sort(array, comparator);
printArray(array);
printStats();
}
/* Stats Functions */
private static void resetStats() {
comparator.cmpCount = cmp2Count = swapCount = 0;
}
private static void printStats() {
System.out.println("tryToReduceSwaps: " + tryToReduceSwaps);
System.out.println("useMiddleAsPivot: " + useMiddleAsPivot);
System.out.println("compoundPivot: " + compoundPivot);
System.out.println("swap: " + swapCount);
System.out.println("cmp1: " + comparator.cmpCount);
System.out.println("(cmp2: " + cmp2Count + ")");
}
/* Main Method */
public static void main(String args[]) {
final int n = args.length;
final int count = n > 0 ? Integer.parseInt(args[0]) : 10;
final int max = n > 1 ? Integer.parseInt(args[1]) : 10;
final Integer[] array = new Integer[count];
for (int i = 0; i < count; ++i) {
array[i] = (int)Math.floor(Math.random() * max);
}
System.out.println("Unsorted");
printArray(array);
System.out.println("\nSorted");
useMiddleAsPivot = false;
tryToReduceSwaps = false;
compoundPivot= false;
customSort(copy(array));
useMiddleAsPivot = false;
tryToReduceSwaps = false;
compoundPivot= true;
customSort(copy(array));
useMiddleAsPivot = false;
tryToReduceSwaps = true;
compoundPivot= true;
customSort(copy(array));
useMiddleAsPivot = true;
tryToReduceSwaps = true;
compoundPivot= true;
customSort(copy(array));
librarySort(copy(array));
}
}