Hi guys,
I'm trying to count and time the comparisons in the mergesort algorithm so that I can compare it to other sorting algorithms. I've managed to get a count and stopwatch 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!
package insertsort;
import java.util.Random;
import java.util.Date;
class ArrayIns
{
private long[] a; // ref to array a
private int nElems; // number of data items
//--------------------------------------------------------------
public ArrayIns(int max) // constructor
{
a = new long [max]; // create the array
nElems = 0; // no items yet
}
//--------------------------------------------------------------
public static void ascending()
{
ArrayIns arrAscending;
int maxSize= 500;
//ascending order array
arrAscending = new ArrayIns(maxSize);
//ascending order array
int i;
for(i=0; i<maxSize;i++)
{
arrAscending.insert(i); // insert 10 items
}
System.out.println("");
System.out.println("ascending list:");
long startTimeNano = System.nanoTime( );
arrAscending.insertionSort();
long taskTimeNano = System.nanoTime( ) - startTimeNano;
System.out.println("insertion sort running time in nano seconds:" + taskTimeNano);
}
public static void descending()
{
ArrayIns arrDescending;
int maxSize=500;
arrDescending = new ArrayIns(maxSize);
int i;
for(i=maxSize; i>0;i--)
{
arrDescending.insert(i); // insert 10 items
}
System.out.println("");
System.out.println("descending list:");
long startTimeNano = System.nanoTime( );
arrDescending.insertionSort();
long taskTimeNano = System.nanoTime( ) - startTimeNano;
System.out.println("insertion sort running time in nano seconds:" + taskTimeNano);
}
public static void repeat()
{
ArrayIns Repeat;
int maxSize=500;
Repeat = new ArrayIns(maxSize);
Random generator = new Random();
int i;
//random array
for(i=0; i<maxSize;i++)
{
Repeat.insert( generator.nextInt( 5)); // insert 10 items
}
System.out.println("");
System.out.println("repeated list:");
long startTimeNano = System.nanoTime( );
Repeat.insertionSort();
long taskTimeNano = System.nanoTime( ) - startTimeNano;
System.out.println("insertion sort running time in nano seconds:" + taskTimeNano);
}
public void insert(long value) // put element into array
{
a[nElems] = value; // insert it
nElems++; // increment size
}
//--------------------------------------------------------------
public void display() // displays array contents
{
for(int j=0; j<nElems; j++) // for each element,
System.out.print(a[j] + " "); // display it
System.out.println("");
}
//--------------------------------------------------------------
public void insertionSort()
{
int in, out;
int count=0;
for(out=1; out<nElems; out++) // out is dividing line
{
long temp = a[out]; // remove marked item
in = out; // start shifts at out
while(in>0 && a[in-1] >= temp) // until one is smaller,
{
count++;
a[in] = a[in-1]; // shift item to right
--in; // go left one position
}
a[in] = temp; // insert marked item
} // end for
System.out.println("Number of comparisons: " + count);
} // end insertionSort()
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];
}
}
System.out.println("Number of comparisons: " + count1 );
}
}
//--------------------------------------------------------------
// end class ArrayIns
////////////////////////////////////////////////////////////////
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;
//random array
for(i=0; i<maxSize;i++)
{
arr.insert( generator.nextInt( 9999)); // insert 10 items
}
System.out.println("list lengths: "+ maxSize);
System.out.println("sorting items with insert sort...");
long startTimeNano = System.nanoTime( );
arr.insertionSort(); // insertion-sort them
long taskTimeNano = System.nanoTime( ) - startTimeNano;
System.out.println("insertion sort running time in nano seconds:" + taskTimeNano);
//ascending order array
ArrayIns.ascending();
ArrayIns.descending();
ArrayIns.repeat();
MergeSortArray marr = new MergeSortArray(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...");
long startTimeNanoMerge = System.nanoTime( );
marr.mergeSort();
long taskTimeNanoMerge = System.nanoTime( ) - startTimeNanoMerge;
System.out.println("merge sort running time in nano seconds:" + taskTimeNanoMerge);
}
}