Computer Science 282 Programming Assignment #3 As always, add whatever is necessary so that the methods below behave correctly. Leave all variables, method names, and code fragments exactly as they appear. Only add code to make the methods work. The method names should make it clear what the method should do. Ask, preferably on Canvas, if you have any questions. A few reminders and rules (ask about these if you have questions!): Your sorts should work on 0-element arrays. Shift rather than swap during insertion and trickling. Be sure your various quicksort methods are making recursive calls to the proper quicksort method. Since there are multiple quicksorts it is easy to accidentally make the wrong recursive calls. The cutoff parameter in your quicksorts represents the smallest sized partition that will be recursively sorted, as described in week 10-lecture.pdf. For example, if cutoff = 10 then a partition with 10 elements will be recursively sorted while a partition of size 9 or less will not. Be sure you get this exactly right. It is easy to be off by 1. Also, don't get thrown off by the way the calculation is done in week 10-lecture.pdf. To be sure the stack does not overflow in your quicksorts write your recursive quicksort methods with a loop that: (1) selects the pivot, (2) partitions the array by calling a partition method, (3) makes the recursive call on the smaller partition(s), and (4) sets parameter values so that the loop simulates the second/third recursive call on the larger/largest partition. The code for QS_OutsideIn_randomPivot below should prove helpful but realize that it gets a little more complicated in the 2-pivot case. When partitioning, whenever an element is encountered that is the same as the pivot assume it is in the correct spot do not move it. // Used to return the two pivots in the 2-pivot partition class Pair { public int left, right; public } } Pair(int left, int right) { this. left = left; this.right right; // Class to hold all the sorts and their associated methods class ArraySorts { public static String myName() { public static void insertionSort(int a[], int n) { public static void QS_OutsideIn_randomPivot (int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); insertionSort (a, n); } private static void QS_OutsideIn_randomPivot (int a[], int lf, int rt, int cutoff) { } int pivot; while ((rt - lf + 1) >= cutoff) { pivot } } = pivot = partitionOutsideIn(a, lf, rt, pivot); lf + (int) (Math.random() * (rt lf + 1)); if ((pivot - lf) < (rt - pivot)) { } } else { QS_OutsideIn_randomPivot (a, lf, pivot-1, cutoff); lf = pivot+1; QS_OutsideIn_randomPivot(a, pivot+1, rt, cutoff); pivot -1; rt = public static void QS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void QuickSort_2Pivot_Both Random (int a[], int n, int cutoff{ public static void QS_Outside In_lfPivot (int a[], int n, int cutoff) { public static void QS_LeftToRight_lfPivot (int a[], int n, int cutoff) { public static void AlmostQS_OutsideIn_randomPivot(int a[], int n, int cutoff) { QS_OutsideIn_randomPivot (a, 0, n - 1, cutoff); public static void AlmostQS_LeftToRight_randomPivot (int a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom (int a[], int n, int cutoff) { public static int partitionLeftToRight (int a[], int lf, int rt, int pivot) { public static void AlmostQS_LeftToRight_randomPivot(int a[], int n, int cutoff) { a[], int n, int cutoff) { public static void AlmostQuickSort_2Pivot_BothRandom(int public static int partitionLeftToRight(int a[], int lf, int rt, int pivot) { public static int partitionOutsideIn(int a[], int lf, int rt, int pivot) { public static Pair partition2 Pivot (int a[], int lf, int rt, int pivotl, public static void HeapSortBottomUp (int a[], int n) { public static void HeapSortTopDown (int a[], int n) { public static void trickleDown (int a[], int lf, int rt) { public static void trickleUp(int a[], int rt) { int pivotr) {