QuickSorting

public class Sorting { 

/**  * Implement quick sort.  *  * Use the provided random object to select your pivots.  * For example if you need a pivot between a (inclusive)  * and b (exclusive) where b > a, use the following code:  *  * int pivotIndex = rand.nextInt(b - a) + a;  *  * It should be:  * in-place  *  * Have a worst case running time of:  * O(n^2)  *  * And a best case running time of:  * O(n log n)  *  * You may assume that the array doesn't contain any null elements.  *  * Note that there may be duplicates in the array.  *  * Make sure you code the algorithm as you have been taught it in class.  * There are several versions of this algorithm and you may not get full  * credit if you do not use the one we have taught you!  *  * @throws IllegalArgumentException if the array or comparator or rand is  * null  * @param  data type to sort  * @param arr the array that must be sorted after the method runs  * @param comparator the Comparator used to compare the data in arr  * @param rand the Random object used to select pivots  */ public static  void quickSort(T[] arr, Comparator comparator, Random rand) { if (arr == null || comparator == null || rand == null) { throw new IllegalArgumentException("Either array, comparator or rand is cannot be null."); } quickSortHelper(arr, comparator, rand, 0, arr.length - 1); } private static  void quickSortHelper(T[] arr, Comparator comparator, Random rand, int start, int end) { if (start < end) { int i = start + 1; int j = end; if (start >= j) { return; } int pivot = rand.nextInt((end+ 1) - start) + start; swap(arr, start, pivot); while (i < j) { if (comparator.compare(arr[i], arr[start]) < 0) { i++; } if (comparator.compare(arr[j], arr[start]) > 0) { j--; } if (start <= end) { swap(arr, i++, j--); } } swap(arr, start, j); if (start < pivot) { quickSortHelper(arr, comparator, rand, start, pivot - 1); } if (end > pivot) { quickSortHelper(arr, comparator, rand, pivot + 1, end); } } } private static  void swap(T[] arr, int index1, int index2) { T temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } 

}

@Test public void testQuickSort() { int[] pivotCounts = {11, 5, 7, 0, 0, 4, 4}; IntStream.range(0, arrays.length).forEach(i -> { comp = StringHolder.getComparatorPlus(); RandomCounter pivotCounter = new RandomCounter(0b10100110011L); StringHolder[] unsorted = arrays[i][0]; StringHolder[] sorted = arrays[i][1]; currentArray = Arrays.toString(unsorted); Sorting.quickSort(unsorted, comp, pivotCounter); assertThat(ARRAYS_UNEQUAL + SORTING_MSG + currentArray, unsorted, is(equalTo(sorted))); if (COUNT_COMPS) { assertThat(INCORRECT_COUNT + SORTING_MSG + currentArray, comp.count(), is(around(comparisons.get("quick").get(i)))); assertThat(TOO_MANY_PIVOTS + SORTING_MSG + currentArray, pivotCounter.count(), is(around(pivotCounts[i]))); } }); }

java.lang.AssertionError: Array was not sorted correctly. Tried to sort: [T, H, E, Q, U, I, C, K, B, R, O, W, N, F, O, X, T] Expected: is [, , , , , , , , , , , , , , , , ] but: was [, , , , , , , , , , , , , , , , ]