In this exercise we will add a counter to the MergeSorter pr

In this exercise, we will add a counter to the MergeSorter program to help us measure the number of comparisons of array elements being made while the routine is completing the sort.

The MergeSorter code is listed below.

The behavior we want to monitor occurs in this section of code,

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.

Modify the main program below so you can test sorting arrays with sizes 10000, 20000, …,90000.

What are your results?

Solution

MergeSort.java

public class MergeSort{
   private static int count; //declaring a count variable to keep count
   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
      count = 0; //intialising count to 0
      // 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 ++;
            count ++; //incrementing count
         }
         else{
            a[j] = second[iSecond];
            iSecond++;
            count ++; //incrementing count
         }
         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++;
      }
   }

   //method that returns the count
   public static int getCounter(){
      return count;
   }

   //method to set count to 0
   public static void resetCounter(){
      count = 0;
   }

   //driver method
   public static void main(String[] args) {
      //delacring range of values for the array
      int n = 100000;

      //iterating through different sizes of both arrays
      for (int i = 10000; i <= 90000; i += 10000){
         for (int j = 10000; j <= 90000; j += 10000){

            //creating arrays of random integers using method from ArrayUtil class
            int first[] = ArrayUtil.randomIntArray(i, n);
            int second[] = ArrayUtil.randomIntArray(j, n);

            //creaing an empty array to store the merged array
            int arr[] = new int[i+j];

            //calling merge function
            merge(first, second, arr);

            //printing out the number of comparisons
            System.out.println(\"For array of sizes \"+i+\" and \"+j+\", the number of comparison operations = \"+getCounter());

            //setting the number of count to 0
            resetCounter();
         }
      }
   }
}

ArrayUtil.java

/**
   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;
   }

}