Count mergesort comparisons

[sam8]

Hi guys,

I'm trying to count the comparisons in the mergesort algorithm so that I can compare it to other sorting algorithms. I've managed to get a count function to work for insertsort but mergesort is being a complete pain!
It's probably a very simple problem but I've experimented around with it and can't get it to work.
I've got an integer (count1) to count comparisons within the mergesort method and then I want to print out the total number of comparisons, however, when the method is called, the output repeats the system.out.println on multiple lines, not adding up the seperate comparisons. The out.println is getting stuck in a loop.
Can someone please tell me what I've done wrong??

Many thanks!

Mergesort method:

public static class MergeSortArray {
  private long[] theArray;

  private int nElems;

  public MergeSortArray(int max) {
    theArray = new long[max];
    nElems = 0;
  }

  public void insert(long value) {
    theArray[nElems] = value; // insert it
    nElems++; // increment size
  }

  public void display() {
    for (int j = 0; j < nElems; j++)
      System.out.print(theArray[j] + " ");
    System.out.println("");
  }

  public void mergeSort() {
    long[] workSpace = new long[nElems];
    recMergeSort(workSpace, 0, nElems - 1);
  }

  private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {

      if (lowerBound == upperBound) // if range is 1,
      return; // no use sorting
    else { // find midpoint
      int mid = (lowerBound + upperBound) / 2;
      // sort low half
      recMergeSort(workSpace, lowerBound, mid);
      // sort high half
      recMergeSort(workSpace, mid + 1, upperBound);
      // merge them
      merge(workSpace, lowerBound, mid + 1, upperBound);
    }
  }

  private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
    int j = 0; // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr - 1;
    int n = upperBound - lowerBound + 1; // # of items
    int count1=0;
    
    while (lowPtr <= mid && highPtr <= upperBound)
    {
      if (theArray[lowPtr] < theArray[highPtr])
      {workSpace[j++] = theArray[lowPtr++];
      count1++;
      }
      else
      { workSpace[j++] = theArray[highPtr++];
         count1++;
      }
    while (lowPtr <= mid)
    { workSpace[j++] = theArray[lowPtr++];
        count1++;
    }
    while (highPtr <= upperBound)
    { workSpace[j++] = theArray[highPtr++];
        count1++;
    }
    for (j = 0; j < n; j++)
    {theArray[lowerBound + j] = workSpace[j];
    }
    }
[B]System.out.println("Number of comparisons: " + count1 );[/B]
  }

}

eg. the output looks like this

sorting items with merge sort...
Number of comparisons: 2
Number of comparisons: 2
Number of comparisons: 4

etc.

[JamesCherrill]

Your print is in the merge method, which gets called repeatedly during the sort, so you get repeated prints.
You need to move the count variable out of the method so it retains its value from one call to the next, and print it only when the sort has finished.

[sam8]

Your print is in the merge method, which gets called repeatedly during the sort, so you get repeated prints.
You need to move the count variable out of the method so it retains its value from one call to the next, and print it only when the sort has finished.

Ok thanks. I've tried moving the print statement out of the merge method, but it wont compile. It says non static variable count1 cannot be referenced from a static context. I've declared the count1 variable at the top of the Merge class, and I don't know how to make it into a static variable because I thought it already is!

Heres the shortened code I'm working with....

Thanks.

*/

package insertsort;
 import java.util.Random;
/**
 *
 * @author sam
 */
 
 

public class  MergeSort1 {
  private long[] theArray;

  private int nElems;

 public int count1=0;



  public MergeSort1(int max) {
    theArray = new long[max];
    nElems = 0;


  }

  public void insert(long value) {
      

    theArray[nElems] = value; // insert it
    nElems++; // increment size
  }

  public void display() {
    for (int j = 0; j < nElems; j++)
      System.out.print(theArray[j] + " ");
    System.out.println("");
  }

  public void mergeSort() {
    long[] workSpace = new long[nElems];
    recMergeSort(workSpace, 0, nElems - 1);
  }

  private void recMergeSort(long[] workSpace, int lowerBound, int upperBound) {

      if (lowerBound == upperBound) // if range is 1,
      return; // no use sorting
    else { // find midpoint
      int mid = (lowerBound + upperBound) / 2;
      // sort low half
      recMergeSort(workSpace, lowerBound, mid);
      // sort high half
      recMergeSort(workSpace, mid + 1, upperBound);
      // merge them
      merge(workSpace, lowerBound, mid + 1, upperBound);


    }
  }

  private void merge(long[] workSpace, int lowPtr, int highPtr, int upperBound) {
    int j = 0; // workspace index
    int lowerBound = lowPtr;
    int mid = highPtr - 1;
    int n = upperBound - lowerBound + 1; // # of items



    while (lowPtr <= mid && highPtr <= upperBound)
    {
      if (theArray[lowPtr] < theArray[highPtr])
      {workSpace[j++] = theArray[lowPtr++];
      count1++;
      }
      else
      { workSpace[j++] = theArray[highPtr++];
         count1++;
      }
    while (lowPtr <= mid)
    { workSpace[j++] = theArray[lowPtr++];
        count1++;
    }
    while (highPtr <= upperBound)
    { workSpace[j++] = theArray[highPtr++];
        count1++;
    }
    for (j = 0; j < n; j++)
    {theArray[lowerBound + j] = workSpace[j];
    }

  }

  }

  public static void main(String[] args)

{

      int maxSize = 500; // array size

// reference to array


 Random generator = new Random();

int i;


  MergeSort1 marr = new MergeSort1(maxSize); // create the array

    for(i=0; i<maxSize;i++)
{

marr.insert( generator.nextInt( 9999)); // insert 10 items

}


    System.out.println("");
    System.out.println("sorting items with merge sort...");

      marr.mergeSort();
      
      System.out.println("number of comparisons:" + count1);
  }
}

[JamesCherrill]

Variables are not static unless you declare them as "static". However, in this case the variable is (correctly) a public instance member, so you can refer to it from main via the instance (just like you call methods on the instance like marr.insert()) as marr.count1

[javaAddict]

count1 is non static. It is an attribute of the MergeSort1 class and must be called the way the non static methods are called:

MergeSort1 marr = new MergeSort1(maxSize);
System.out.println("Number of comparisons: " + marr.count1 );

When you are inside the class MergeSort1 you are ok, because it is a member of that class. But in the main you create an instance of that class, so you need to access the count1 of that class:

MergeSort1 marr1 = new MergeSort1(maxSize);
marr1.count1;

MergeSort1 marr2 = new MergeSort1(maxSize);
marr2.count1;

MergeSort1 marr3 = new MergeSort1(maxSize);
marr3.count1;

Those 3 count1s are different. Each one belongs to their instance and it is not a rule that they will have the same value. For different arrays they will return different results

[sam8]

Variables are not static unless you declare them as "static". However, in this case the variable is (correctly) a public instance member, so you can refer to it from main via the instance (just like you call methods on the instance like marr.insert()) as marr.count1

Thanks! I understand it now