QuickSorting } java.lang.AssertionError: Array was not sorted correctly. Tried t
ID: 3738902 • Letter: Q
Question
QuickSorting
}
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 [<B>, <C>, <E>, <F>, <H>, <I>, <K>, <N>, <O>, <O>, <Q>, <R>, <T>, <T>, <U>, <W>, <X>]
but: was [<H>, <R>, <X>, <O>, <E>, <Q>, <O>, <W>, <U>, <B>, <F>, <C>, <T>, <I>, <K>, <N>, <T>]
Explanation / Answer
Can you try with the below Code
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 <T> 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 <T> void quickSort(T[] arr, Comparator<T> 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 <T> int partition(T[] arr, Comparator<T> compare, int p, int q)
{
T piv = arr[q];
int i = (p-1);
for (int j=p; j<q; j++)
{
if (compare.compare(arr[j] ,piv)<=0)
{
i++;
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
T temp = arr[i+1];
arr[i+1] = arr[q];
arr[q] = temp;
return i+1;
}
private static <T> void quickSortHelper(T[] arr, Comparator<T> comparator,
Random rand, int start, int end) {
if (start < end)
{
int pi = partition(arr, comparator ,start, end);
quickSortHelper(arr,comparator,rand, start, pi-1);
quickSortHelper(arr, comparator,rand, pi+1, end);
}
}
private static <T> void swap(T[] arr, int index1, int index2) {
T temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
========
Let me know if there is any issue/concern.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.