Having some trouble implementing the mergeSort method, lsdradix method, and quic

Question

 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);     } } 

Explanation / Answer

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);
}
}
}

=============================================================================================

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.