Call / Test Sorting Methods in Main Class

Question

For reference I am programming Java in BlueJ.

I am fairly new to the language and I am having trouble with sorting.

I am trying to call / test all of the 5 sorting methods in the main class.

I figured out how to call / test Quicksort:

Sorting.quickSort(friends, 0, friends.length-1);

But the others are not working correctly. Specifically these:

Sorting.mergeSort(friends, 0, friends.length-1);

Sorting.PbubbleSort(friends, 0, friends.length-1);

Sorting.PinsertionSort(friends, 0, friends.length-1);

Sorting.selectionSort(friends, 0, friends.length-1);

Hopefully somebody can assist me.

For reference, this is the output when it is not sorted:

Smith, John     610-555-7384
Barnes, Sarah   215-555-3827
Riley, Mark     733-555-2969
Getz, Laura     663-555-3984
Smith, Larry    464-555-3489
Phelps, Frank   322-555-2284
Grant, Marsha   243-555-2837

This is the output when it is sorted:

Barnes, Sarah   215-555-3827
Getz, Laura     663-555-3984
Grant, Marsha   243-555-2837
Phelps, Frank   322-555-2284
Riley, Mark     733-555-2969
Smith, John     610-555-7384
Smith, Larry    464-555-3489

This is the class Sorting, which I should note is all correct:

 public class Sorting{
    /**
     * Swaps to elements in an array. Used by various sorting algorithms.
     * 
     * @param data the array in which the elements are swapped
     * @param index1 the index of the first element to be swapped
     * @param index2 the index of the second element to be swapped
     */
    private static <T extends Comparable<? super T>> void swap(T[] data,
            int index1, int index2){
        T temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    /**
     * Sorts the specified array of objects using the quick sort algorithm.
     * @param data the array to be sorted
     */
    public static <T extends Comparable<? super T>> void quickSort(T[] data){
        quickSort(data, 0, data.length - 1);
    }

    /**
     * Recursively sorts a range of objects in the specified array using the
     * quick sort algorithm. The parameters min and max represent the range of
     * values on which the sort is performed.
     * 
     * @param data the array to be sorted
     * @param min the minimum index in the range to be sorted
     * @param max the maximum index in the range to be sorted
     */
    public static <T extends Comparable<? super T>> void quickSort(T[] data,
            int min, int max){
        if (min < max){
            // create partitions
            int indexofpartition = partition(data, min, max);

            // sort the left partition (lower values)
            quickSort(data, min, indexofpartition - 1);

            // sort the right partition (higher values)
            quickSort(data, indexofpartition + 1, max);
        }
    }

    /**
     * Used by the quick sort algorithm to find the partition.
     * 
     * @param data the array to be sorted
     * @param min the minimum index in the range to be sorted
     * @param max the maximum index in the range to be sorted
     */
    private static <T extends Comparable<? super T>> int partition(
            T[] data, int min, int max){
       T partitionelement;
       int left, right;
       int middle = (min + max) / 2;

       // use the middle data value as the partition element
       partitionelement = data[middle];
       // move it out of the way for now
       swap(data, middle, min);

       left = min;
       right = max;

       while (left < right){
          // search for an element that is > the partition element
          while (left < right && data[left].compareTo(partitionelement) <= 0)
             left++;

          // search for an element that is < the partition element
          while (data[right].compareTo(partitionelement) > 0)
             right--;

          // swap the elements
          if (left < right)
             swap(data, left, right);
        }

       // move the partition element into place
       swap(data, min, right);

       return right;
    }

    /**
    * Sorts the specified array of objects using the merge sort
    * algorithm.
    *
    * @param data  the array to be sorted
    * @param min   the integer representation of the minimum value 
    * @param max   the integer representation of the maximum value
    */
    public static <T extends Comparable<? super T>> void mergeSort (T[] data, int min, int max){
       T[] temp;
       int index1, left, right;

       /** return on list of length one */
       if (min==max)
          return; 

       /** find the length and the midpoint of the list */
       int size = max - min + 1;
       int pivot = (min + max) / 2;
       temp = (T[])(new Comparable[size]);

       mergeSort(data, min, pivot); // sort left half of list
       mergeSort(data, pivot + 1, max); // sort right half of list

       /** copy sorted data into workspace */
       for (index1 = 0; index1 < size; index1++)
          temp[index1] = data[min + index1];

       /** merge the two sorted lists */
       left = 0;
       right = pivot - min + 1;
       for (index1 = 0; index1 < size; index1++){
          if (right <= max - min)
             if (left <= pivot - min)
                if (temp[left].compareTo(temp[right]) > 0)
                   data[index1 + min] = temp[right++];

                else
                   data[index1 + min] = temp[left++];
             else
                data[index1 + min] = temp[right++];
          else
             data[index1 + min] = temp[left++];
       }
    }

    public static <T extends Comparable<? super T>> void PbubbleSort(T[] theArray, int n) {
       // ---------------------------------------------------
       // Sorts the items in an array into ascending order.
       // Precondition: theArray is an array of n items.
       // Postcondition: theArray is sorted into ascending
       // order.  From Prichard&Carrano
       // ---------------------------------------------------
       boolean sorted = false;  // false when swaps occur

       for (int pass = 1; (pass < n) && !sorted; ++pass) {
          // Invariant: theArray[n+1-pass..n-1] is sorted
          //            and > theArray[0..n-pass]
          sorted = true;  // assume sorted
          for (int index = 0; index < n-pass; ++index) {
             // Invariant: theArray[0..index-1] <= theArray[index]
             int nextIndex = index + 1;
             if (theArray[index].compareTo(theArray[nextIndex]) > 0) {
                // exchange items
                T temp = theArray[index];
                theArray[index] = theArray[nextIndex];
                theArray[nextIndex] = temp;
                sorted = false;  // signal exchange
             }  // end if
          }  // end for

          // Assertion: theArray[0..n-pass-1] < theArray[n-pass]
       }  // end for
    }  // end bubbleSort

    public static <T extends Comparable<? super T>> void PinsertionSort(T[] theArray, int n) {
       // ---------------------------------------------------
       // Sorts the items in an array into ascending order.
       // Precondition: theArray is an array of n items.
       // Postcondition: theArray is sorted into ascending
       // order. FROM PRITCHARD & CARRANO
       // ---------------------------------------------------
       // unsorted = first index of the unsorted region,
       // loc = index of insertion in the sorted region,
       // nextItem = next item in the unsorted region

       // initially, sorted region is theArray[0],
       //          unsorted region is theArray[1..n-1];
       // in general, sorted region is theArray[0..unsorted-1],
       //          unsorted region is theArray[unsorted..n-1]

       for (int unsorted = 1; unsorted < n; ++unsorted) {
          // Invariant: theArray[0..unsorted-1] is sorted

          // find the right position (loc) in
          // theArray[0..unsorted] for theArray[unsorted],
          // which is the first item in the unsorted
          // region; shift, if necessary, to make room
          T nextItem = theArray[unsorted];
          int loc = unsorted;

          while ((loc > 0) &&
                (theArray[loc-1].compareTo(nextItem) > 0)) {
             // shift theArray[loc-1] to the right
             theArray[loc] = theArray[loc-1];
             loc--;
          }  // end while
          // Assertion: theArray[loc] is where nextItem belongs
          // insert nextItem into sorted region
          theArray[loc] = nextItem;
       }  // end for
    }  // end insertionSort 

    public static <T extends Comparable<? super T>> void selectionSort (T[] data){
       int min;
       T temp;

       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 the values */
          temp = data[min];
          data[min] = data[index];
          data[index] = temp;
       }
    }
}

Main class, SortPhoneList:

public class SortPhoneList{
   /**
    * Creates an array of Contact objects, sorts them, then prints
    * them.
    */
   public static void main (String[] args){

      Contact[] friends = new Contact[7];

      friends[0] = new Contact ("John", "Smith", "610-555-7384");
      friends[1] = new Contact ("Sarah", "Barnes", "215-555-3827");
      friends[2] = new Contact ("Mark", "Riley", "733-555-2969");
      friends[3] = new Contact ("Laura", "Getz", "663-555-3984");
      friends[4] = new Contact ("Larry", "Smith", "464-555-3489");
      friends[5] = new Contact ("Frank", "Phelps", "322-555-2284");
      friends[6] = new Contact ("Marsha", "Grant", "243-555-2837");


      Sorting.quickSort(friends, 0, friends.length-1);

      Sorting.mergeSort(friends, 0, friends.length-1);

      Sorting.PbubbleSort(friends, 0, friends.length-1);

      Sorting.PinsertionSort(friends, 0, friends.length-1);

      Sorting.selectionSort(friends, 0, friends.length-1);


      for (int index = 0; index < friends.length; index++)
         System.out.println (friends[index]);
   }

Answer 1

Those sorting algorithms are all working fine. (Given the varying style of comments, I gather that you collected those from different sources on the internet or from books.)

The problem is that you are calling them the wrong way. Note that those different methods have different parameters: Some require just the data to be sorted, some the length of the data, some the length minus one. This information can be found in the documentation at the top of each of the methods.

Try this main method for testing the individual sorts:

public static void main(String[] args) {

    // create random test data
    Random random = new Random();
    Integer[] data = new Integer[50];
    for (int i = 0; i < data.length; i++) {
        data[i] = random.nextInt(100);
    }

    // print unsorted data
    System.out.println(Arrays.asList(data));
    // uncomment the algorithm you want to test
    quickSort(data);
//  mergeSort(data, 0, data.length - 1);
//  selectionSort(data);
//  PinsertionSort(data, data.length);
//  PbubbleSort(data, data.length);
    // print sorted data
    System.out.println(Arrays.asList(data));
}