Computer Science 210
Data Structures

Fall 2017, Siena College

SortingComparisons BlueJ Project

Click here to download a BlueJ project for SortingComparisons.


SortingComparisons Source Code

The Java source code for SortingComparisons is below. Click on a file name to download it.


SortingComparisons.java

import structure5.*;

/**
   Comparisons of advanced sorting procedures, operating on arrays of
   Comparable elements

   @author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu
*/

public class SortingComparisons {

    /**
       Make a copy of an array

       @param a array to be cloned
       @return new array containing same objects as a
    */
    protected static Integer[] clone(Integer[] a) {

	Integer copy[] = new Integer[a.length];
	for (int i=0; i<a.length; i++) {
	    copy[i] = a[i];
	}
	return copy;
    }

    /**
       Main method to compare sorting procedures <BR>
       Takes the size of an array of Intgers to be generated as its
       only command-line parameter.<BR>
       Sorts with each of several procedures, timing them.<BR>
       Prints the times taken by each procedure for random data, 
       ascending data, descending data.<BR>

       @param args command-line parameter: args[0] is array length
    */
    public static void main(String[] args) {

	// pull array size from command line parameter
	if (args.length != 1) {
	    System.out.println("Usage: java SortingComparisons arrayLength");
	    return;
	}
	int i, n;
	try {
	    n = (new Integer(args[0]));
	}
	catch(NumberFormatException e) {
	    System.out.println("Usage: java SortingComparisons arrayLength");
	    return;
	}

	// make sure we have at least 2 elements (normally should be 
	// much larger, of course)
	if (n < 2) {
	    System.out.println("Specify array size of at least 2.");
	    return;
	}
       
	// create some arrays to work with, one with random values in the
	// range 0 to 2n, then an ascending array and a descending array,
	// using the same values for consistency
	    
	System.out.println("Generating random arrays of size " + n + ".");
	Integer randomData[] = new Integer[n];
	java.util.Random r = new java.util.Random();
	for (i = 0; i < n; i++) {
	    randomData[i] = r.nextInt(2*n);
	}
	Integer ascendingData[] = clone(randomData);
	QuickSort.quickSort(ascendingData);

	Integer descendingData[] = new Integer[n];
	for (i = 0; i < n; i++) {
	    descendingData[i] = ascendingData[n-1-i];
	}

	// set up for our sorting tests
	// in each case, we clone one of the input arrays (so we can sort
	// it without destroying the original), then time one of the
	// sorting algorithms

	// note the mechanism to call a static method in another class:
	// ClassName.methodName()
	long startTime, duration;
	Integer data[];


	/* Selection Sort */
	System.out.println("Selection sort:");

	data = clone(randomData);

	startTime = System.currentTimeMillis();
	SelectionSort.selSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	SelectionSort.selSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	SelectionSort.selSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

	/* Insertion Sort */
	System.out.println("Insertion sort:");
	data = clone(randomData);

	startTime = System.currentTimeMillis();
	InsertionSort.insSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	InsertionSort.insSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	InsertionSort.insSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

	/* Merge Sort */
	System.out.println("Merge sort:");
	data = clone(randomData);

	startTime = System.currentTimeMillis();
	MergeSort.mergeSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	MergeSort.mergeSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	MergeSort.mergeSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

	/* Heap Sort */
	System.out.println("Heap sort:");
	data = clone(randomData);

	startTime = System.currentTimeMillis();
	HeapSort.heapSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	HeapSort.heapSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	HeapSort.heapSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

	/* Tree Sort */
	System.out.println("Tree sort:");
	data = clone(randomData);

	startTime = System.currentTimeMillis();
	BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
	for (i=0; i<n; i++) bst.add(data[i]);
	java.util.Iterator<Integer> iter = bst.iterator();
	i=0;
	while (iter.hasNext()) {
	    data[i++] = iter.next();
	}
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	bst = new BinarySearchTree<Integer>();
	for (i=0; i<n; i++) bst.add(data[i]);
	iter = bst.iterator();
	i=0;
	while (iter.hasNext()) {
	    data[i++] = iter.next();
	}
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	bst = new BinarySearchTree<Integer>();
	for (i=0; i<n; i++) bst.add(data[i]);
	iter = bst.iterator();
	i=0;
	while (iter.hasNext()) {
	    data[i++] = iter.next();
	}
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

	/* Quick Sort */
	System.out.println("Quicksort:");
	data = clone(randomData);

	startTime = System.currentTimeMillis();
	QuickSort.quickSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tRandom input: " + duration + " ms");

	data = clone(ascendingData);

	startTime = System.currentTimeMillis();
	QuickSort.quickSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tAscending input: " + duration + " ms");

	data = clone(descendingData);

	startTime = System.currentTimeMillis();
	QuickSort.quickSort(data);
	duration = System.currentTimeMillis()-startTime;

	System.out.println("\tDescending input: " + duration + " ms");

    }
}

SelectionSort.java

/**
   Recursive selection sort on an array of Comparable objects

   @author Jim Teresco, terescoj@cs.williams.edu
*/
public class SelectionSort {

    /**
       recursive method to do a selection sort on an array of Comparable objects
       @param array array of Comparable elements
       @post array is sorted in ascending order
    */
    public static <T extends Comparable> void selSort(T[] array) {
	
	recSelSort(array.length-1, array);
    }

    /**
       helper method to do the actual recursive selection sort

       @param lastIndex the index beyond which the array is already sorted
       @param array the array of Comparable elements
       @pre array is sorted from position lastIndex to array.length-1
       @post array is sorted
    */
    protected static <T extends Comparable> 
				void recSelSort(int lastIndex, T[] array) {
	// stopping condition: is there more than 1 element left to sort?
	if (lastIndex > 0) {
	    int extreme = 0;    // to store the index of largest element
	    
	    // Search for that index of the largest element
	    for (int searchIndex = 1; searchIndex <= lastIndex; searchIndex++) {
		if (array[extreme].compareTo(array[searchIndex]) < 0)
		    extreme = searchIndex;
	    }
	    
	    // swap largest element (at extreme) with the one at lastIndex
	    T temp = array[extreme];
	    array[extreme] = array[lastIndex];
	    array[lastIndex] = temp;
	    // Assert: array[lastIndex] now largest in array[0..lastIndex]
	    
	    recSelSort(lastIndex-1,array);
	    // Assert: array[0..lastIndex] are sorted.
	}
    }
}

InsertionSort.java

/**
   Recursive insertion sort of an array of Comparable objects

   @author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu
*/
public class InsertionSort {

    /**
       recursive method to do a insertion sort on an array of Comparable objects
       @param array array of Comparable elements
       @post array is sorted in ascending order
    */
    public static <T extends Comparable> void insSort(T[] array) {
	
	recInsSort(array.length-1, array);
    }

    /**
       helper method to do the actual recursive insertion sort

       @param lastIndex the index beyond which the array is already sorted
       @param array the array of Comparable elements
       @pre array is sorted from position lastIndex to array.length-1
       @post array is sorted
    */
    protected static <T extends Comparable> void 
		     recInsSort(int lastIndex, T[] array) {
	// stopping condition: is there more than 1 element to sort?
	if (lastIndex > 0) {

	    // first sort 0..lastIndex-1, recursively
	    recInsSort(lastIndex-1, array);

	    // position is index where last will be inserted
	    int position = lastIndex-1;  

	    // search for first element (from rear) which is <= array[lastIndex]
	    while (position >= 0 && 
		   array[lastIndex].compareTo(array[position]) < 0)
		position--;
	    
	    position++; // insert array[index] at position
	    
	    // move array[position .. last-1] to put in array[last]
	    T temp = array[lastIndex];
	    for (int moveIndex = lastIndex-1; moveIndex >= position; moveIndex--)
		array[moveIndex+1] = array[moveIndex];
	    
	    // insert element into proper position
	    array[position] = temp;
	    // now array[0..last] are in order, return to caller
	}
    }
}

MergeSort.java

/**
   Merge sort, based heavily on Java Structures example that
   sorts array of int rather than array of Comparable

   @author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu
*/
public class MergeSort {

    /**
       method to do a mergesort on an array of Comparable objects

       @param array array of Comparable elements
       @post array is sorted in ascending order
    */
    public static <T extends Comparable> void mergeSort(T array[]) {
	mergeSortRecursive(array,(T[])(new Comparable[array.length]),
			   0, array.length-1);
    }
    
    // pre: 0 <= low <= high < array.length
    // post: values in array[low..high] are in ascending order
    private static <T extends Comparable> 
			      void mergeSortRecursive(T array[], 
						      T temp[], 
						      int low, int high) {
	int n = high - low + 1;
	int middle = low + n/2;
	int i;

	if (n < 2) return;
	// move lower half of array into temporary storage
	for (i = low; i < middle; i++) {
	    temp[i] = array[i];
	}
	// sort lower half of array
	mergeSortRecursive(temp, array, low, middle-1);
	// sort upper half of array
	mergeSortRecursive(array, temp, middle, high);
	// merge halves together
	merge(array, temp, low, middle, high);
    }
    
    // pre: array[middle..high] are ascending
    //      temp[low..middle-1] are ascending
    // post: array[low..high] contains all values in ascending order
    private static <T extends Comparable> 
			      void merge(T array[], T temp[],
					 int low, int middle, int high) {
	int ri = low; // result index
	int ti = low; // temp index
	int di = middle; // destination index
	// while two lists are not empty merge smaller value
	while (ti < middle && di <= high) {
	    if (array[di].compareTo(temp[ti]) < 0) {
		array[ri++] = array[di++]; // smaller is in high array
	    } else {
		array[ri++] = temp[ti++]; // smaller is in temp
	    }
	}
	// possibly some values left in temp array
	while (ti < middle) {
	    array[ri++] = temp[ti++];
	}
	// ...or some values left (in correct place) in array
    }

    // pre: 0 <= i,j < array.length
    // post: array[i] and array[j] are exchanged
    public static <T extends Comparable> void swap(T array[], int i, int j) {
	T temp;
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
    }
}

HeapSort.java

/**
   Heap sort on an array of Comparable objects

   @author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu
*/
public class HeapSort {

    /**
       method to do a heap sort on an array of Comparable objects

       @param array array of Comparable elements
       @post array is sorted in ascending order
    */
    public static <T extends Comparable> void heapSort(T[] array) {
	// We first need to "heapify", thinking of the elements in the
	// array as being in an array representation of binary trees.
	// Helper methods below get the indices of parent and
	// left/right children.  Since we wish to sort the data in
	// ascending order, the heap must be a Max-Heap.  Elements in
	// the second half of the array are already trivial heaps, so
	// we start the process at the first location that has one or
	// two children.

	// index of the last element in the array
	int last = array.length-1;

	// for each position that has children, working backwards,
	// we treat it as a root being added to a heap, essentially
	// the pushDownRoot method of VectorHeap.
	for (int index = (last-1)/2; index >= 0; index--) {
	    pushDownRoot(array, index, array.length);
	}

	// we now have a valid heap we extract elements in reverse
	// sorted order, putting them at the end of the heap and into
	// their final position.  After each step, we need to heapify

	for (int index = last; index > 0; index--) {
	    T temp = array[index];
	    array[index] = array[0];
	    array[0] = temp;

	    pushDownRoot(array, 0, index);
	}
    }

    // next three methods borrowed from structure.VectorHeap
    /**
     * Returns parent index
     * @param i a node index
     * @return parent of node at i
     * @pre 0 <= i < size
     * @post returns parent of node at location i
     */
    protected static int parent(int i) {
	return (i-1)/2;
    }
    
    /**
     * Returns left child index.
     * @param i a node index
     * @return left child of node at i
     * @pre 0 <= i < size
     * @post returns index of left child of node at location i
     */
    protected static int left(int i) {
	return 2*i+1;
    }
    
    /**
     * Returns right child index.
     * @param i a node index
     * @return right child of node at i
     * @pre 0 <= i < size
     * @post returns index of right child of node at location i
     */
    protected static int right(int i) {
	return 2*(i+1);
    }

    /**
     * This method based heavily on structure.VectorHeap.pushDownRoot
     * Moves node downward, into appropriate position within a subheap.
     * This method assumes a Max-Heap structure.
     * @param array array of elements containing heap or near heap
     * @param root index of the root of the subheap
     * @param maxHeap index beyond which we do not have or want a heap
     * @pre 0 <= root < maxHeap
     * @post moves node at index root down to appropriate position in subtree
     */
    protected static <T extends Comparable> void pushDownRoot(T array[], 
				       int root, int maxHeap) {
	T value = array[root];
	while (root < maxHeap) {
	    int childPos = left(root);
	    if (childPos < maxHeap) {
		if ((right(root) < maxHeap) &&
		    (array[childPos+1].compareTo(array[childPos]) > 0)) {
		    childPos++;
		}
		// Assert: childPos indexes larger of two children
		if (array[childPos].compareTo(value) > 0) {
		    array[root] = array[childPos];
		    root = childPos; // keep moving down
		} else { // found right location
		    array[root] = value;
		    return;
		}
	    } else { // at a leaf! insert and halt
		array[root] = value;
		return;
	    }	    
	}
    }
}

QuickSort.java

/**
   Quicksort, based heavily on Java Structures example that
   sorts array of int rather than array of Comparable

   @author Jim Teresco, terescoj@cs.williams.edu, jteresco@siena.edu
*/
public class QuickSort {

    /**
       method to do a quicksort on an array of Comparable objects

       @param array array of Comparable elements
       @post array is sorted in ascending order
    */
    public static <T extends Comparable> void quickSort(T[] array) {

	quickSortRecursive(array, 0, array.length-1);
    }

    // pre: left <= right
    // post: array[left] placed in the correct (returned) location
    private static <T extends Comparable> int partition(T array[], 
							int left, int right) {
	while (true)
	{
	    // move right "pointer" toward left
	    while (left < right && array[left].compareTo(array[right]) < 0)
		right--;
	    if (left < right) swap(array, left++, right);
	    else return left;
	    // move left pointer toward right
	    while (left < right && array[left].compareTo(array[right]) < 0)
		left++;
	    if (left < right) swap(array, left, right--);
	    else return right;
	}
    }
	
    // pre: left <= right
    // post: array[left..right] in ascending order
    private static <T extends Comparable> void quickSortRecursive(T array[],
					   int left, int right) {
	int pivot;   // the final location of the leftmost value
	if (left >= right) return;
        pivot = partition(array, left, right);    /* 1 - place pivot */
	quickSortRecursive(array, left, pivot-1); /* 2 - sort small */
	quickSortRecursive(array, pivot+1, right);/* 3 - sort large */
        /* done! */
    }


    // pre: 0 <= i,j < array.length
    // post: array[i] and array[j] are exchanged
    public static <T extends Comparable> void swap(T array[], int i, int j) {
	T temp;
	temp = array[i];
	array[i] = array[j];
	array[j] = temp;
    }
}