0

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);

}

}
1
Contributor
1
Reply
3
Views
6 Years
Discussion Span
Last Post by sam8
This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.