Question

In: Computer Science

24.10 Lab Ch24: MergeSortDouble Create a class MergeSortDouble and implement a sort(double[]) method using merge sort...

24.10 Lab Ch24: MergeSortDouble

Create a class MergeSortDouble and implement a sort(double[]) method using merge sort algorithm.

Test will call the sort() method.

java please!

Solutions

Expert Solution

import java.util.Arrays;

public class MergeSortDouble {

    /**
     * Recursive helper method for merging arr[l..m] and arr[m+1..r]
     *
     * @param arr
     * @param l
     * @param m
     * @param r
     */
    static void merge(double[] arr, int l, int m, int r) {
        double[] first = new double[m - l + 1];
        double[] second = new double[r - m];
        // copy array arr[l..m] into first
        for (int i = 0; i < first.length; i++)
            first[i] = arr[l + i];
        // copy array arr[m+1..r] into second
        for (int i = 0; i < second.length; i++)
            second[i] = arr[m + 1 + i];
        int ind1 = 0, ind2 = 0, i = l;
        // merge first and second arrays into arr[l..r]
        while (ind1 < first.length || ind2 < second.length) {
            if (ind2 >= second.length || (ind1 < first.length && first[ind1] < second[ind2])) {
                arr[i++] = first[ind1++];
            } else if (ind1 >= first.length || second[ind2] < first[ind1]) {
                arr[i++] = second[ind2++];
            }
        }
    }

    /**
     * Recursive merge sortArray helper method
     *
     * @param arr
     * @param l
     * @param r
     */
    static void sort(double[] arr, int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // SortAll first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /**
     * merge sortArray method with the normal array input parameter
     *
     * @param arr
     */
    static void sort(double[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    // Testing the method here
    public static void main(String[] args) {
        double[] arr = {0.1, 5, 10.5, 9.8, 3.3, 5.6, 8.5, 7.3, 1.5, 99.9, 30};
        System.out.println("Original array: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}


Related Solutions

(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list...
(Write a C# program DO NOT USE CLASS)Implement the merge sort algorithm using a linked list instead of arrays. You can use any kind of a linked structure, such as single, double, circular lists, stacks and/or queues. You can populate your list from an explicitly defined array in your program. HINT: You will not be using low, middle and high anymore. For finding the middle point, traverse through the linked list while keeping count of the number of nodes. Break...
Language: Java Implement Merge Sort
Language: Java Implement Merge Sort
IN MATLAB!! Q6. Create a 1D array of numbers and implement ‘Merge Sort’ in MATLAB to...
IN MATLAB!! Q6. Create a 1D array of numbers and implement ‘Merge Sort’ in MATLAB to sort it in ascending order
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that...
USING JAVA Almost sort the array using Merge Sort. Perform Merge Sort as usual except that during the final merge, it is not necessary to merge all n elements, but only the elements in positions 1 to k.
Java program to implement the merge sort your own and test it to sort a list...
Java program to implement the merge sort your own and test it to sort a list of names based on the frequency.
implement merge sort,quick sort, and radix sort algorithms in java and test how long it will...
implement merge sort,quick sort, and radix sort algorithms in java and test how long it will take to sort with random data sets of users input numbers.
java please        * implement zip method in Q1 class to merge two linkedlists into...
java please        * implement zip method in Q1 class to merge two linkedlists into one.        * The elements in the result are made by concatenating elements in different        * linkedlists one after one. The order of the elements matters.        * For example, merge(list1, list2) should return [1,5,2,4,3,3,4,2,5,1].        * You can assume that arr1 and arr2 has the same size.        * HINT: You should use ListIterator to make it...
write a java merge sort called MERGE-SORT-A(), Using recursive calls and NO INSERTION-SORT() as a sub-procedure.
write a java merge sort called MERGE-SORT-A(), Using recursive calls and NO INSERTION-SORT() as a sub-procedure.
Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content...
Sorting (merge) Sort the array (as in Part 2) using merge sort. Write the array content after each pass (i.e., from pass 1 to pass 9). Each pass is defined as the completion of one merge operation. Suppose an array contains the following integers: -1, 20, 10, -5, 0, -7, 100, -7, 30, -10. Sort the array using the following algorithms: selection sort, bubble sort, and insertion sort. For each algorithm, write the array content after each pass (i.e., from...
Write a program in Java to sort the given array using merge sort, quick sort, insertion...
Write a program in Java to sort the given array using merge sort, quick sort, insertion sort, selection sort and bubble sort based on the input from the user which sorting technique they wanted to use. Get the array size, array elements from the user, and also display the sorted array along with the name of the sorting technique used.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT