Please add a counter to the MergeSorter program to measure the number of compari
ID: 3683771 • Letter: P
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 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
Explanation / Answer
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Surya
*/
//you have to sent the complete code ... so i cant run... but i am sure... this will definitely work...
class MergeSorter{
static int counter=0;//declare counter as public variabe in MergeSorter class... and initialize to zero..
static int getCounter()//added method to return counter value...
{
return counter;
}
static void resetCounter()//added method to reseting counter to zero..
{
counter = 0;
}
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];counter++;//added code to count the comparisions...
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++;
}
}
}
/**
This class contains utility methods for array manipulation.
*/
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;
}
}
/**
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)
{
//Modified program test sorting arrays with sizes 10000, 20000, …,90000
int i=10000;
for(i=10000;i<=90000;i=i+10000)
{int[] a = ArrayUtil.randomIntArray(i,i);
MergeSorter.resetCounter();
MergeSorter.sort(a);
System.out.println("Array size: 10000; comparisons: " + MergeSorter.getCounter());
}
}
}
// comment if ur satisfied with this answer...
//if u have any doubts... feel free to ask
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.