Question
Please add a counter to the MergeSorter program to measure the number of comparisons of array elements being made while the routine is completing the
Please add a counter to the MergeSorter program to measure the number of comparisons of array elements being made while the routine is completing the sort.
private static void merge(int[] first, int[] second, int[] a) { int iFirst = 0; // Next element to consider in the first array int iSecond = 0; // Next element to consider in the second array int j = 0; // Next open position in a // As long as neither iFirst nor iSecond is past the end, move // the smaller element into a while (iFirst < first.length && iSecond < second.length) { if (first[iFirst] < second[iSecond]) { a[j] = first[iFirst]; iFirst++; } else { a[j] = second[iSecond]; iSecond++; } j++; } // Note that only one of the two loops below copies entries // Copy any remaining entries of the first array while (iFirst < first.length) { a[j] = first[iFirst]; iFirst++; j++; } // Copy any remaining entries of the second half while (iSecond < second.length) { a[j] = second[iSecond]; iSecond++; j++; } }
The behavior we want to monitor occurs in this section of code,
if (first[iFirst] < second[iSecond]) { a[j] = first[iFirst]; iFirst++; } else { a[j] = second[iSecond]; iSecond++; }
It is in the above section that we compare array elements and decide which element becomes part of our merged and sorted array. By counting the number of comparisons here, we obtain a measurement that helps us gauge the speed of the algorithm. Add code that will count each comparison, maintaining the result in an integer counter. Supply a method getCounter to retrieve the counter. Supply a second method called resetCounter to set the counter to 0.
The code below supports creating and swapping elements in arrays of varying sizes.
/** This class contains utility methods for array manipulation. */ public class ArrayUtil { /** Creates an array filled with random values. @param length the length of the array @param n the number of possible random values @return an array filled with length numbers between 0 and n - 1 */ public static int[] randomIntArray(int length, int n) { int[] a = new int[length]; for (int i = 0; i < a.length; i++) { a[i] = (int) (Math.random() * n); } return a; } /** Swaps two entries of an array. @param a the array @param i the first position to swap @param j the second position to swap */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }
Modify the main program below so we can test sorting arrays with sizes 10000, 20000, ,90000.
/** This program demonstrates the merge sort algorithm by sorting an array that is filled with random numbers. */ public class MergeSortDemo { public static void main(String[] args) { int[] a = ArrayUtil.randomIntArray(10000, 10000); MergeSorter.resetCounter(); MergeSorter.sort(a); System.out.println("Array size: 10000; comparisons: " + MergeSorter.getCounter()); } }
What are the results?
1) Modified Mergesorter class
2) Modified MergeSortDemo class
3) Results
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started