1
\$\begingroup\$

I am posting the code for my merge sort to see if I can get folks offer suggestions as to where to make comparisons or if I am making the correctly already.

I will post my heap sort and quick sorts in other posts. I actually have them all in a package that runs them together but separating them out for clarity.

package AlgorithmComparison;

import java.util.*;
import java.math.*;

public class AlgCompareApp
{
  public static void main(String[] args)
  {
  int mSortCnt = 0;
  int numbersNeeded = 5000;  // Number in the array 
  double total = logb(numbersNeeded,2);
  double logN = numbersNeeded * total;
  int loopCount = 50;  // Change this for the Loop through each sort

  System.out.print("n log(n) for " + numbersNeeded + " is ");
  System.out.printf(" %.2f",logN);
  System.out.println();
  System.out.println("Merge Sort");
    for(int l = 0; l < loopCount; l++) 
    {
    Random rng = new Random();
    // Create initial Array List of numbers
    ArrayList<Integer> arrlist = new ArrayList<Integer>();

    // Populate Initial Array List with numbers and no duplicates
    for (int i = 0; i < numbersNeeded; i++)
    {
      while (true)
      {
        Integer next = rng.nextInt(numbersNeeded * 2);
        if (!arrlist.contains(next))
        {
          arrlist.add(next);
          break;
        }
      }
    }

    // Create QuickSort Int Array from ArrayList
    int[] mergeSortArray = new int[arrlist.size()];
    for (int i = 0; i < arrlist.size(); i++)
    {
      mergeSortArray[i] = arrlist.get(i);
    }
    //System.out.print("\n---------------Merge Sort---------------\n");
    MergeSortRun mgsrt = new MergeSortRun();
    mgsrt.MergeSortRun(mergeSortArray, 0, mergeSortArray.length - 1);
    mgsrt.displayList();
    mSortCnt = mSortCnt +mgsrt.getCounterOne();
      }
    System.out.println("Averages");
    System.out.println((mSortCnt / loopCount));
    System.out.println("Percentage of n log(n)");
    System.out.printf("%.2f",((mSortCnt / loopCount)/logN));
    System.out.println();
  }

  public static double logb( double a, double b )
{
return Math.log(a) / Math.log(b);
}
}

package AlgorithmComparison;

import java.util.*;

public class MergeSortRun
{
    private int counterOne = 0;
   int[] displayList;

  public void MergeSortRun(int array[], int lo, int n)
  {
    int low = lo;
    int high = n;
    if (low >= high)
    {
      return;
    }
    int middle = (low + high) / 2;
    MergeSortRun(array, low, middle);
    MergeSortRun(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;
    while ((lo <= end_low) && (start_high <= high))
    {
      if (array[low] < array[start_high])
      {
        low++;
      } else
      {
        int Temp = array[start_high];
        for (int k = start_high - 1; k >= low; k--)
        {
          array[k + 1] = array[k];
        }
        array[low] = Temp;
        low++;
        end_low++;
        start_high++;
        //counterOne++;
      }
      counterOne++;
    }
    // counterOne++;
    displayList = Arrays.copyOf(array, n + 1);
  }

  public void displayList()
  {
//    for (int i = 0; i < displayList.length; i++)
//    {
//      System.out.print(displayList[i] + " ");
//    }
    System.out.println(counterOne);
  }

  public int getCounterOne()
  {
    return counterOne;
  }
}

My entire java package is zipped up and can be downloaded from here.

\$\endgroup\$
  • \$\begingroup\$ You seem to be asking us to find bugs in your code. That's not the purpose of this site. The best (and certainly a quicker) way to find bugs is to write unit tests yourself, and use a Java debugger yourself. \$\endgroup\$ – Stephen C Jun 23 '13 at 4:59
  • \$\begingroup\$ I am sorry if you thought I was asking for the code to be debugged, my intent was really to get folks who had more experience to look at where I was making comparisons and see if they thought I was counting the comparisons correctly. Or better yet, how they might do it versus how I did it in my code. \$\endgroup\$ – wfsteadman Jun 23 '13 at 14:09
2
\$\begingroup\$

Here's some suggestions on what you can do differently to get a better result (both performance counters and code style).

The MergeSortRun class breaks many rules for naming conventions in Java.... well, actually the class name is OK (MergeSortRun), but the method (also called MergeSortRun) is very confusing, because only the constructor (which you don't have coded up) is supposed to have that name.

Rename the MergeSortRun method to something simple like 'sort'.

Additionally, the variables 'counterOne' and 'displaylist' are not necessary... if it were me, I would have 'counterOne' returned from the sort method, and the displaylist variable is completely dead anyway. Doing this will allow you to make the sort method static, of the form:

public static final int sort(int array[], int lo, int n) {...}

The 'int' return value is the number of comparisons you want to count.

Now, you have to question what your counter should be. There are two key items that tend to impact performance of sorts. The one is comparisons, and the other is data-moves (or swaps).

Since your input data is an int[] array, the comparisons between values are just as expensive as any other int based comparison. Thus, I think you should potentially be counting much more. The easiest way to do it is to show you what I think it should look like:

public int sort(int array[], int lo, int n) {
    int low = lo;
    int high = n;
    int compares = 1;
    if (low >= high) {
        return compares;  // NOTE - 1 comparison (low >= high)
    }
    int middle = (low + high) / 2; // technically should be: (low + high) >>> 1
    compares += sort(array, low, middle);
    compares += sort(array, middle + 1, high);
    int end_low = middle;
    int start_high = middle + 1;
    while ((lo <= end_low) && (start_high <= high)) {
        compares += 3; // two in 'while' loop above, and one in 'if' below.
        if (array[low] < array[start_high]) {
            low++;
        } else {
            int Temp = array[start_high];
            compares++; // entry in to the for loop
            for (int k = start_high - 1; k >= low; k--) {
                array[k + 1] = array[k];
                compares++; // exit from the for loop
            }
            array[low] = Temp;
            low++;
            end_low++;
            start_high++;
        }
    }
    return compares;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.