Homework Help is Here – Start Your Trial Now!
Engineering
Data Structures and Algorithms
provided code: import java.util.Comparator; import java.util.List; import java.util.LinkedList; import java.util.Queue; /**  * Your implementation of various divide & conquer sorting algorithms.  */ public class Sorting {     /**      * Implement merge sort.      *      * It should be:      * out-of-place      * stable      * not adaptive      *      * 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 merge sort, but at the end, everything      * should be merged back into the original T[] which was passed in.      *      * When splitting the array, if there is an odd number of elements, put the      * extra data on the right side.      *      * Hint: You may need to create a helper method that merges two arrays      * back into the original T[] array. If two data are equal when merging,      * think about which subarray you should pull from first.      *      * You may assume that the passed in array and comparator are both valid      * and will not be null.      *      * @param        Data type to sort.      * @param arr        The array to be sorted.      * @param comparator The Comparator used to compare the data in arr.      */     public static void mergeSort(T[] arr, Comparator comparator) {         // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!     }     /**      * Implement LSD (least significant digit) radix sort.      *      * It should be:      * out-of-place      * stable      * not adaptive      *      * Have a worst case running time of: O(kn)      * And a best case running time of: O(kn)      *      * Feel free to make an initial O(n) passthrough of the array to      * determine k, the number of iterations you need.      *      * At no point should you find yourself needing a way to exponentiate a      * number; any such method would be non-O(1). Think about how how you can      * get each power of BASE naturally and efficiently as the algorithm      * progresses through each digit.      *      * You may use an ArrayList or LinkedList if you wish, but it should only      * be used inside radix sort and any radix sort helpers. Do NOT use these      * classes with merge sort. However, be sure the List implementation you      * choose allows for stability while being as efficient as possible.      *      * Do NOT use anything from the Math class except Math.abs().      *      * You may assume that the passed in array is valid and will not be null.      *      * @param arr The array to be sorted.      */     public static void lsdRadixSort(int[] arr) {         // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!     } }

provided code: import java.util.Comparator; import java.util.List; import java.util.LinkedList; import java.util.Queue; /**  * Your implementation of various divide & conquer sorting algorithms.  */ public class Sorting {     /**      * Implement merge sort.      *      * It should be:      * out-of-place      * stable      * not adaptive      *      * 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 merge sort, but at the end, everything      * should be merged back into the original T[] which was passed in.      *      * When splitting the array, if there is an odd number of elements, put the      * extra data on the right side.      *      * Hint: You may need to create a helper method that merges two arrays      * back into the original T[] array. If two data are equal when merging,      * think about which subarray you should pull from first.      *      * You may assume that the passed in array and comparator are both valid      * and will not be null.      *      * @param        Data type to sort.      * @param arr        The array to be sorted.      * @param comparator The Comparator used to compare the data in arr.      */     public static void mergeSort(T[] arr, Comparator comparator) {         // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!     }     /**      * Implement LSD (least significant digit) radix sort.      *      * It should be:      * out-of-place      * stable      * not adaptive      *      * Have a worst case running time of: O(kn)      * And a best case running time of: O(kn)      *      * Feel free to make an initial O(n) passthrough of the array to      * determine k, the number of iterations you need.      *      * At no point should you find yourself needing a way to exponentiate a      * number; any such method would be non-O(1). Think about how how you can      * get each power of BASE naturally and efficiently as the algorithm      * progresses through each digit.      *      * You may use an ArrayList or LinkedList if you wish, but it should only      * be used inside radix sort and any radix sort helpers. Do NOT use these      * classes with merge sort. However, be sure the List implementation you      * choose allows for stability while being as efficient as possible.      *      * Do NOT use anything from the Math class except Math.abs().      *      * You may assume that the passed in array is valid and will not be null.      *      * @param arr The array to be sorted.      */     public static void lsdRadixSort(int[] arr) {         // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!     } }

icon
Related questions
Question

provided code:

import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Your implementation of various divide & conquer sorting algorithms.
 */

public class Sorting {

    /**
     * Implement merge sort.
     *
     * It should be:
     * out-of-place
     * stable
     * not adaptive
     *
     * 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 merge sort, but at the end, everything
     * should be merged back into the original T[] which was passed in.
     *
     * When splitting the array, if there is an odd number of elements, put the
     * extra data on the right side.
     *
     * Hint: You may need to create a helper method that merges two arrays
     * back into the original T[] array. If two data are equal when merging,
     * think about which subarray you should pull from first.
     *
     * You may assume that the passed in array and comparator are both valid
     * and will not be 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) {
        // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
    }

    /**
     * Implement LSD (least significant digit) radix sort.
     *
     * It should be:
     * out-of-place
     * stable
     * not adaptive
     *
     * Have a worst case running time of: O(kn)
     * And a best case running time of: O(kn)
     *
     * Feel free to make an initial O(n) passthrough of the array to
     * determine k, the number of iterations you need.
     *
     * At no point should you find yourself needing a way to exponentiate a
     * number; any such method would be non-O(1). Think about how how you can
     * get each power of BASE naturally and efficiently as the algorithm
     * progresses through each digit.
     *
     * You may use an ArrayList or LinkedList if you wish, but it should only
     * be used inside radix sort and any radix sort helpers. Do NOT use these
     * classes with merge sort. However, be sure the List implementation you
     * choose allows for stability while being as efficient as possible.
     *
     * Do NOT use anything from the Math class except Math.abs().
     *
     * You may assume that the passed in array is valid and will not be null.
     *
     * @param arr The array to be sorted.
     */
    public static void lsdRadixSort(int[] arr) {
        // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
    }
}

For this assignment you will be coding 2 different sorts: Merge Sort and LSD Radix Sort. For merge sort, the autograder will be looking at the number of comparisons made between elements to test for efficiency. For each sorting algorithm, you may assume that the array you are sorting will not contain null elements. You should also assume that the array may contain any number of duplicate elements. Your implementations should match what was taught in this course. IMPORTANT: • You will be given 5 attempts on this assignment, with a 30 minute cooldown between submissions. • Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below. Comparator Merge sort will take in a Comparator, which is used to compare two elements. You must use this Comparator, as the number of comparisons performed with it will be used when testing your assignment. The comparator is used as follows: comparator.compare (A, B) will return: <0 if A is less than B • • > 0 if A is greater than B • O if A is equal to B Generic Methods Most of the assignments is this course so far have utilized generics by incorporating them into the class declaration. However, the rest of the assignments will have you implement various algorithms as static methods in a utility class. Thus, the generics from here on will use generic methods instead of generic classes (hence the <T> in each of the method headers and javadocs). This also means any helper methods you create will also need to be static with the same <T> in the method header. Merge Sort Merge sort should be out-of-place, stable, and not adaptive. It should have a worst case running time of O (nlogn) and a best case running time of O (nlogn). When splitting an odd size array, the extra data should go on the right. LSD Radix Sort LSD Radix sort should be out-of-place, stable, and not adaptive. It should have a worst case running time of O (kn) and a best case running time of O (kn), where k is the number of digits in the longest number. You will be implementing the least significant digit version of the sort. You will be sorting ints. Note that you CANNOT change the ints into Strings at any point in the sort. The sort must be done in base 10. You may use Math.abs() when finding the largest magnitude number. However, be wary of handling overflow if you use Math.abs()! General Tips • For LSD Radix sort, you cannot take the absolute value of Integer.MIN_VALUE, as it does not fit in a Java int. How should you account for this edge case when initially searching for the largest magnitude number? • We highly recommend copying the starter code and working in your preferred IDE in order to have access to features such as code completion, auto-formatting, and much more! Here are general assignment guidelines that should be followed.
Transcribed Image Text:For this assignment you will be coding 2 different sorts: Merge Sort and LSD Radix Sort. For merge sort, the autograder will be looking at the number of comparisons made between elements to test for efficiency. For each sorting algorithm, you may assume that the array you are sorting will not contain null elements. You should also assume that the array may contain any number of duplicate elements. Your implementations should match what was taught in this course. IMPORTANT: • You will be given 5 attempts on this assignment, with a 30 minute cooldown between submissions. • Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below. Comparator Merge sort will take in a Comparator, which is used to compare two elements. You must use this Comparator, as the number of comparisons performed with it will be used when testing your assignment. The comparator is used as follows: comparator.compare (A, B) will return: <0 if A is less than B • • > 0 if A is greater than B • O if A is equal to B Generic Methods Most of the assignments is this course so far have utilized generics by incorporating them into the class declaration. However, the rest of the assignments will have you implement various algorithms as static methods in a utility class. Thus, the generics from here on will use generic methods instead of generic classes (hence the <T> in each of the method headers and javadocs). This also means any helper methods you create will also need to be static with the same <T> in the method header. Merge Sort Merge sort should be out-of-place, stable, and not adaptive. It should have a worst case running time of O (nlogn) and a best case running time of O (nlogn). When splitting an odd size array, the extra data should go on the right. LSD Radix Sort LSD Radix sort should be out-of-place, stable, and not adaptive. It should have a worst case running time of O (kn) and a best case running time of O (kn), where k is the number of digits in the longest number. You will be implementing the least significant digit version of the sort. You will be sorting ints. Note that you CANNOT change the ints into Strings at any point in the sort. The sort must be done in base 10. You may use Math.abs() when finding the largest magnitude number. However, be wary of handling overflow if you use Math.abs()! General Tips • For LSD Radix sort, you cannot take the absolute value of Integer.MIN_VALUE, as it does not fit in a Java int. How should you account for this edge case when initially searching for the largest magnitude number? • We highly recommend copying the starter code and working in your preferred IDE in order to have access to features such as code completion, auto-formatting, and much more! Here are general assignment guidelines that should be followed.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 1 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer