Homework SourseHaving some trouble implementing the mergeSort method lsdrad
Having some trouble implementing the mergeSort method, lsdradix method, and quicksort in java. Need some help completing my code. Thanks! /** * Implement merge sort. * * It should be: * stable * * Have a worst case running time of: * O(n log n) * * And a best case running time of: * O(n log n) * * You can create more arrays to run mergesort, but at the end, * everything should be merged back into the original T[] * which was passed in. * * Any duplicates in the array should be in the same relative position after * sorting as they were before sorting. * * @throws IllegalArgumentException if the array or comparator is null * @param <T> data type to sort * @param arr the array to be sorted * @param comparator the Comparator used to compare the data in arr */ public static <T> void mergeSort(T[] arr, Comparator<T> comparator) { if (arr == null || comparator == null) { throw new IllegalArgumentException(\"Array or comparator cannot\" + \" be null.\"); } if (arr.length < 2) { return; //if the array only has one element, then it is sorted } int halfLength = arr.length / 2; T[] arr1 = (T[]) new Object[halfLength + 1]; T[] arr2 = (T[]) new Object[halfLength + 1]; for (int i = 0; i < halfLength; i++) { arr1[i] = arr[i]; } for (int j = halfLength; j < arr.length; j++) { for (int k = 0; k < arr2.length; k++) { arr2[k] = arr[j]; } } mergeSort(arr1, comparator); mergeSort(arr2, comparator); mergeHelper(arr1, arr2, arr, comparator); } /** * A helper method for mergeSort that sorts the two halves and merges * them back together. * @param firstHalf the first half of the array * @param secondHalf the second half of the array * @param arr the array we are sorting * @param comparator the Comparator used to compare the data in arr * @param <T> data type to sort */ private static <T> void mergeHelper(T[] firstHalf, T[] secondHalf, T[] arr, Comparator<T> comparator) { int i = 0; int j = 0; while (i + j < arr.length) { if (j == secondHalf.length || (i < firstHalf.length && comparator.compare(firstHalf[i], secondHalf[j]) < 0)) { arr[i + j] = firstHalf[i]; i++; } else { arr[i + j] = secondHalf[j]; j++; } } } /** * Implement LSD (least significant digit) radix sort. * * Remember you CANNOT convert the ints to strings at any point in your * code! * * It should be: * stable * * Have a worst case running time of: * O(kn) * * And a best case running time of: * O(kn) * * Any duplicates in the array should be in the same relative position after * sorting as they were before sorting. (stable) * * Do NOT use {@code Math.pow()} in your sort. Instead, if you need to, use * the provided {@code pow()} method below. * * You may use {@code java.util.ArrayList} or {@code java.util.LinkedList} * if you wish, but it may only be used inside radix sort and any radix sort * helpers. Do NOT use these classes with other sorts. * * @throws IllegalArgumentException if the array is null * @param arr the array to be sorted * @return the sorted array */ public static int[] lsdRadixSort(int[] arr) { if (arr == null) { throw new IllegalArgumentException(\"Array or comparator cannot\" + \" be null.\"); } return null; } /** * 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 = r.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) * * 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(\"Neither array, comparator, nor\" + \" rand can be null.\"); } if (arr.length < 2) { return; //if the array only has one element, then it is sorted } int left = 0; } /** * Calculate the result of a number raised to a power. Use this method in * your radix sorts instead of {@code Math.pow()}. * * DO NOT MODIFY THIS METHOD. * * @throws IllegalArgumentException if both {@code base} and {@code exp} are * 0 * @throws IllegalArgumentException if {@code exp} is negative * @param base base of the number * @param exp power to raise the base to. Must be 0 or greater. * @return result of the base raised to that power */ private static int pow(int base, int exp) { if (exp < 0) { throw new IllegalArgumentException(\"Exponent cannot be negative.\"); } else if (base == 0 && exp == 0) { throw new IllegalArgumentException( \"Both base and exponent cannot be 0.\"); } else if (exp == 0) { return 1; } else if (exp == 1) { return base; } int halfPow = pow(base, exp / 2); if (exp % 2 == 0) { return halfPow * halfPow; } else { return halfPow * pow(base, (exp / 2) + 1); } } Solution
Points of reference in merge sort -
i)stable
ii)Have a worst case running time of O(kn)
iii)And a best case running time of O(kn)
iv)Any duplicates in the array should be in the same relative position after
sorting as they were before sorting. (stable)
v)Please \'do not\' use {@code Math.pow()} in your sort. Instead, when you require, use
the provided {@code pow()} method below(Radix sort).
vi) You may use {@code java.util.ArrayList} or {@code java.util.LinkedList}
@throws IllegalArgumentException if the array is null
@param arr the array to be sorted
@return the sorted array
==========================================================================================
Radix -
@throws IllegalArgumentException //if both {@code base0001} and {@code exp1} are 0.
@throws IllegalArgumentException //if {@code exp1} is not positive(negative)
@param base0001 //base of the number
@param exp1 //power to raise the base to. Must be 0 or greater.
@return //result of the base raised to that power
{
if (exp1 < 0) {
throw new IllegalArgumentException("Exponent cannot be negative.");
} else if (base0001 == 0 && exp1 == 0) {
throw new IllegalArgumentException(
"Both base and exponent cannot be 0.");
} else if (exp1 == 0) {
return 1;
} else if (exp1 == 1) {
return base0001;
}
int result = pow(base0001, exp1 / 2);
if (exp1 % 2 == 1) {
return result * result * base0001;
} else {
return result * result;}}}
===========================================================================================
Quick Sort -
// import util files in java
import java.util.*;
import javax.swing.JOptionPane;
public class Quicklysorter {
public static void main(String[] args) {
String arraylength = JOptionPane.showInputDialog(\"Enter the length of the array.\");
int a = Integer.parseInt(arraylength); // parsing to integer value, calculating array length
if (a == 0) {
System.out.println(\"Null Length\");
} else {
int[] list = new int[a];
for (int i = 0; i < a; i++) {
String input = JOptionPane.showInputDialog(\"Input the number.\"); // storing the input value from the dialogue pane
int c = Integer.parseInt(input);
list[i] = c;
}
System.out.println(\"Before\");
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + \" \");
}
partition(list, 0, list.length - 1);
System.out.println(\"\ After partitionaing\");
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + \" \");
}
sorter(list, 0, list.length - 1);
System.out.println(\"\ After Sorting\");
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + \" \");
}
}
}
private static int partition(int[] list, int first, int last) { //partitioning in quick sort
int pivot = list[first];
int low = first + 1;
int high = last;
while (high > low) {
while (low < high && list[low] < pivot) {
low++;
}
while (low < high && list[high] >= pivot) {
high--;
}
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot) {
high--;
}
if (pivot > list[high]) {
list[first] = list[high];
list[high] = pivot;
return high;
} else {
return first;
}
}
private static void sorter(int[] list, int first, int last) { //overloading of \'sorter\' method
if (last > first) {
int pivotIndex = partition(list, first, last);
sorter(list, first, pivotIndex - 1);
sorter(list, pivotIndex + 1, last);
}
}
}
=============================================================================================
