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 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 System.out.println("comparisons:" + count1 ); is getting stuck in a loop.
Can someone please tell me what I've done wrong??
Many thanks!
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
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];
}
}
System.out.println("comparisons:" + count1);
}
public static void main(String[] args)
{
int maxSize = 500; // array size
ArrayIns arr; // reference to array
arr = new ArrayIns(maxSize);
// create the 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();
}
}