Learning about sorting need some help?

Question

I have the code below that I have found. I am trying to learn which sorting method is the fastest and which ones use the most and least comparisons. Anyone have any idea how I can add some code in here to do that? I want to tally the total number of comparisons of each sort.

//***********************************************************************************
//  Sorting.java
//
//  Contains various sort algorithms that operate on an array of comparable objects.
//
//************************************************************************************

public class Sorting

{

//------------------------------------------------------------------------------------
//  Sorts the specified array of integers using the selection sort algorithm.
//------------------------------------------------------------------------------------

public static void selectionSort (Comparable[] data)
{
  int min;

  for (int index = 0; index < data.length-1; index ++)
  {
     min = index;
      for (int scan = index+1; scan < data.length; scan++)
        if (data[scan].compareTo(data[min]) < 0)
            min = scan;

      swap (data, min, index);

  }
}
//---------------------------------------------------------------------------------------
//  Swaps to elements in the specified array.
//---------------------------------------------------------------------------------------

private static void swap (Comparable[] data, int index1, int index2)
{
   Comparable temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;

}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using an insertion sort algorithm.
//---------------------------------------------------------------------------------------

public static void insertionSort (Comparable[] data)
{
  for (int index = 1; index < data.length; index++)
  {
    Comparable key = data[index];
     int position = index;

     // shift larger values to the right
     while (position > 0 && data[position-1].compareTo(key) > 0)
     {
       data[position] = data[position-1];
        position--;
     }

     data[position] = key;

    }
}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using a bubble sort algorithm.
//---------------------------------------------------------------------------------------

public static void bubbleSort (Comparable[] data)
{
  int position, scan;

  for (position = data.length - 1; position >= 0; position--)
  {
     for (scan = 0; scan <= position - 1; scan ++)
       if (data[scan].compareTo(data[scan+1]) >0)
          swap (data, scan, scan+1);

    }
}

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the quick sort algorithm.
//---------------------------------------------------------------------------------------

public static void quickSort (Comparable[] data, int min, int max)
{
  int pivot;

  if (min < max)
  {
    pivot = partition (data, min, max); // make partitions
     quickSort(data, min, pivot-1);  //sort left paritions
     quickSort(data, pivot+1, max);  //sort right paritions
  }
}
//---------------------------------------------------------------------------------------
//  Creates the partitions needed for quick sort.
//---------------------------------------------------------------------------------------

public static int partition (Comparable[] data, int min, int max)
{
  //Use first element as the partition value
  Comparable partitionValue = data[min];

  int left = min;
  int right = max;

  while (left < right)
  {
    // Search for an element that is greater than the partition element
     while (data[left].compareTo(partitionValue) <= 0 && left < right)
       left++;

    // Search for an element that is less than the partition element
    while (data[right].compareTo(partitionValue) > 0)
      right--;

    if (left < right)
      swap (data, left, right);

    }

    // Move the partition element to its final position
    swap (data, min, right);

    return right; 
  }

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------

public static void mergeSort (Comparable[] data, int min, int max)
{
  if (min < max)
  {
    int mid = (min + max) / 2;
     mergeSort(data, min, mid);
     mergeSort(data, mid+1, max);
     merge (data, min, mid, max);

  }
 }

//---------------------------------------------------------------------------------------
//  Sorts the specified array of objects using the merge sort algorithm.
//---------------------------------------------------------------------------------------

public static void merge (Comparable[] data, int first, int mid, int last)
{
  Comparable[] temp = new Comparable[data.length];

  int first1 = first, last1 = mid; //endpoints of first subarray
  int first2 = mid + 1, last2 = last; //endpoints of second subarray
  int index = first1; // next index open in temp array

  // Copy smaller item from each subarry into temp until one of the subarrays is exhausted

  while (first1 <= last1 && first2 <= last2)
  {
    if (data[first1].compareTo(data[first2]) < 0)
     {
       temp[index] = data[first1];
        first1++;
     }
     else
     {
       temp[index] = data[first2];
        first2++;
     }
    index++;
  }
 //  Copy remaining elements from first subarray, if any
 while (first1 <= last1)
 {
   temp[index] = data[first1];
    first1++;
    index++;
 }

 //  Copy remaining elements from second subarray, if any
 while (first2 <= last2)
 {
   temp[index] = data[first2];
    first2++;
    index++;
 }

 // Copy merged data into original array
 for (index = first; index <= last; index++)
   data[index] = temp[index];
 }
 }

Answer 1

You should define an abstract class that implements the counting, and then some derived classes that implement the algorithms. The main program would look like this:

List<String> list = new ArrayList<String>();
// TODO: add some elements to the list
SortingAlgorithm alg = new BubbleSort();
alg.sort(list);
alg.printSummary();

Now the abstract class that implements the counting:

public abstract class SortingAlgorithm<T> {

  /* the actual algorithm, which uses the compare and swap methods. */
  public abstract void sort(List<T> list);

  private long compares = 0;
  private long swaps = 0;

  protected int compare(T a, T b) {
    compares++;
    return a.compareTo(b);
  }

  protected void swap(int index1, int index2) {
    swaps++;
    // TODO: do the actual swapping
  }

  public void printSummary() {
    // TODO
  }
}

The concrete algorithms now only have to implement the sort method. How to do this is left as an excercise for the reader.

Answer 2

Rather learn about O-notation from a good book like:

http://www.amazon.com/Data-Structures-Algorithms-Java-2nd/dp/0672324539

Answer 3

If you're interested in speed, use Arrays.sort(). If you're academically interested in what's involved in various sorting techniques, it's probably faster to just look at Wikipedia. If you want us to do your homework for you...we won't, sorry.

Edit: I guess it's fair for me to say this: Is there any reason you couldn't just initialize an integer to 0 at the start of each method, increment it every time something interesting happened, and then print it at the end?