Computer Science 210
Data Structures
Fall 2018, 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.
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");
}
}
/**
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.
}
}
}
/**
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
}
}
}
/**
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;
}
}
/**
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, 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;
}
}