import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.nio.BufferOverflowException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Scanner;
/**
* This is an implementation of various sorting algorithms.
*
* @author Jade Cheng
* @assignment ICS 211 Sorting Algorithms
* @date April 28, 2010
* @bugs None
*/
public class ChengJadeSort {
/**
* A class thrown by the main method when it detects an error.
*/
@SuppressWarnings("serial")
private static class ProgramException extends RuntimeException {
/**
* Initializes a new instance of the MyException class.
*
* @param message
* The message.
*/
public ProgramException(final String message) {
super(message);
}
}
/**
* The main entry point of the program.
*
* @param args
* The command line arguments.
*/
public static void main(final String[] args) {
// Check the command line arguments for usage errors.
if (args.length != 3) {
System.out.println(
"Usage: java ChengJadeSort filePath sortMethod iterations\n"
+ "\n"
+ " filePath The path to a text file containing integers\n"
+ " sortMethod The algorithm used to sort the numbers\n"
+ " iterations The number of times to sort the values\n"
+ "\n"
+ "The 'sortMethod' must be one of the following values:\n"
+ "\n"
+ " 'bubble' --> uses Bubble Sort\n"
+ " 'insertion' --> uses Insertion Sort\n"
+ " 'merge' --> uses Merge Sort\n"
+ " 'quick' --> uses Quick Sort\n"
+ " 'selection' --> uses Selection Sort\n"
+ " 'heap' --> uses Heap Sort\n"
+ "\n"
+ "When the program executes, it loops 'iterations' number of times.\n"
+ "For each iteration i, the program sorts i number of values from\n"
+ "the specified file. After each iteration, the program writes to\n"
+ "standard output the number of items sorted and the number of\n"
+ "operations performed by the specified sorting method. The output\n"
+ "is tab-delimited.\n"
+ "\n"
+ "When the program terminates, it saves the sorted output to the\n"
+ "text file 'sorted.txt'. Each integer is placed on a separate\n"
+ "line.");
return;
}
final String filePath = args[0];
final String sortMethod = args[1];
final String iterationsText = args[2];
try {
// Read the number of iterations and check for errors.
final int iterations;
try {
iterations = Integer.parseInt(iterationsText);
if (iterations <= 0)
throw new ProgramException("'iterations' must be a positive number.");
} catch (final NumberFormatException e) {
throw new ProgramException("'iterations' must be a positive number.");
}
// Determine the method to sort the numbers and check for errors.
final Sorter<Integer> sorter;
if (sortMethod.equalsIgnoreCase("bubble"))
sorter = new BubbleSort<Integer>();
else if (sortMethod.equalsIgnoreCase("insertion"))
sorter = new InsertionSort<Integer>();
else if (sortMethod.equalsIgnoreCase("merge"))
sorter = new MergeSort<Integer>();
else if (sortMethod.equalsIgnoreCase("quick"))
sorter = new QuickSort<Integer>();
else if (sortMethod.equalsIgnoreCase("selection"))
sorter = new SelectionSort<Integer>();
else if (sortMethod.equalsIgnoreCase("heap"))
sorter = new HeapSort<Integer>();
else
throw new ProgramException("'sortMethod' is invalid.");
// Open the file for reading and check for errors.
final Scanner scanner;
try {
final File file = new File(filePath);
scanner = new Scanner(file);
} catch (final FileNotFoundException e) {
throw new ProgramException("'" + filePath + "' is not found.");
}
// Read the maximum number of values from the file.
final Integer[] unsorted = new Integer[iterations];
for (int i = 0; i < iterations; i++) {
try {
unsorted[i] = Integer.valueOf(scanner.nextInt());
} catch (final InputMismatchException e) {
throw new ProgramException("Non-integer value detected in file.");
} catch (final NoSuchElementException e) {
throw new ProgramException("Not enough integers present in file.");
}
}
// Loop the number of iterations specified on the command line. For
// each iteration, copy the unsorted values, sort them, and display
// the results. Also, as a sanity check, ensure the array is sorted
// after each iteration.
for (int i = 1; i <= iterations; i++) {
final Integer[] copy = Arrays.copyOfRange(unsorted, 0, i);
System.out.println(i + "\t" + sorter.sort(copy));
verifySortedArray(copy);
}
// Finally, save the sorted output to the file 'sorted.txt'.
try {
final PrintStream stream = new PrintStream("sorted.txt");
sorter.sort(unsorted);
for (final Integer i : unsorted)
stream.println(i);
} catch (final FileNotFoundException e) {
throw new ProgramException("Cannot write to file 'sorted.txt'");
}
} catch (final ProgramException e) {
// Display errors to standard error and return a failure status.
System.err.println(e.getMessage());
System.exit(1);
}
}
/**
* This method swaps two values in an array.
*
* @param array
* The array.
* @param n
* The first index.
* @param m
* The second index.
*/
public static <T> void swap(final T[] array, final int n, final int m) {
assert n >= 0;
assert m >= 0;
assert n < array.length;
assert m < array.length;
final T temp = array[n];
array[n] = array[m];
array[m] = temp;
}
/**
* Ensures an array of integers is sorted.
*
* @param array
* The array of integers.
*/
private static void verifySortedArray(final Integer[] array) {
for (int i = 1; i < array.length; i++)
if (array[i].compareTo(array[i - 1]) < 0)
throw new ProgramException("Sorted algorithm failed.");
}
}
/**
* This generic class performs a bubble sort.
*/
class BubbleSort<T extends Comparable<T>> implements Sorter<T> {
/**
* Sorts an array using bubble sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
int operations = 0;
boolean isSwapped;
do {
isSwapped = false;
for (int i = 0; i < array.length - 1; i++) {
operations++;
if (array[i].compareTo(array[i + 1]) > 0) {
ChengJadeSort.swap(array, i, i + 1);
isSwapped = true;
}
}
} while (isSwapped);
return operations;
}
}
/**
* This class implements a generic heap. The maximum size of the heap is
* MAX_ELEMENTS.
*/
class Heap<T extends Comparable<T>> {
/** The maximum number of elements that can exist in the heap. */
public static final int MAX_ELEMENTS = 10000;
/** An array that implements the heap buffer. */
private final ArrayList<T> myArray = new ArrayList<T>(Heap.MAX_ELEMENTS);
/** The number of elements used in the array. */
private int mySize = 0;
/**
* Initializes a new instance of the Heap class.
*/
public Heap() {
// Initialize the array of elements all to null.
for (int i = 0; i < Heap.MAX_ELEMENTS; i++)
this.myArray.add(null);
}
/**
* This method adds an item to the heap. This method does not allow null
* values to be added to the collection, but it does allow duplicates.
*
* @param o
* element whose presence in this collection is to be ensured.
*
* @return The number of operations performed.
*
* @throws BufferOverflowException
* Thrown if the item cannot be added.
*/
public int add(final T o) throws BufferOverflowException {
if (o == null)
throw new NullPointerException();
int operations = 0;
if (this.mySize == Heap.MAX_ELEMENTS)
throw new BufferOverflowException();
this.set(this.mySize++, o);
int n = this.mySize - 1;
while (n > 0) {
operations++;
final int nParent = (n - 1) / 2;
if (o.compareTo(this.get(nParent)) >= 0)
break;
this.swap(n, nParent);
n = nParent;
}
return operations;
}
/**
* Compares to elements at the specified index values.
*
* @param left
* The index of the left value.
* @param right
* The index of the right value.
*
* @return The result of the compareTo method.
*/
private int compare(final int left, final int right) {
assert left >= 0;
assert left < this.mySize;
assert right >= 0;
assert right < this.mySize;
assert this.mySize <= this.myArray.size();
return this.get(left).compareTo(this.get(right));
}
/**
* This method returns an element at the specified index.
*
* @param index
* The index.
* @return The element at the specified index.
*/
private T get(final int index) {
assert index >= 0;
assert index < this.mySize;
assert this.mySize <= this.myArray.size();
return this.myArray.get(index);
}
/**
* Retrieves and removes the smallest value in the heap. This method differs
* from the poll method in that it throws an exception if this heap is
* empty.
*
* @return The smallest value in the heap and the number of operations
* performed.
*
* @throws NoSuchElementException
* if this queue is empty.
*/
public Pair<T> remove() throws NoSuchElementException {
if (this.mySize == 0)
throw new NoSuchElementException();
int operations = 0;
final T result = this.get(0);
this.set(0, this.get(this.mySize - 1));
this.set(this.mySize - 1, null);
this.mySize--;
int n = 0;
while (true) {
final int nLeft = n * 2 + 1;
final int nRight = n * 2 + 2;
operations++;
if (nLeft >= this.mySize)
break;
if (nRight >= this.mySize || this.compare(nLeft, nRight) < 0) {
if (this.compare(nLeft, n) >= 0)
break;
this.swap(nLeft, n);
n = nLeft;
continue;
}
if (this.compare(nRight, n) >= 0)
break;
this.swap(nRight, n);
n = nRight;
}
return new Pair<T>(result, operations);
}
/**
* This method sets a value in the heap array.
*
* @param index
* The index of the value to set.
* @param value
* The value to set.
*/
private void set(final int index, final T value) {
assert index >= 0;
assert index < this.mySize;
assert this.mySize <= this.myArray.size();
this.myArray.set(index, value);
}
/**
* This method swaps two values.
*
* @param n
* The first index.
* @param m
* The second index.
*/
private void swap(final int n, final int m) {
assert n >= 0;
assert m >= 0;
assert n < this.mySize;
assert m < this.mySize;
assert this.mySize <= this.myArray.size();
final T temp = this.get(n);
this.set(n, this.get(m));
this.set(m, temp);
}
}
/**
* This class performs a heap sort.
*/
class HeapSort<T extends Comparable<T>> implements Sorter<T> {
/**
* Sorts an array using heap sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
int operations = 0;
final Heap<T> heap = new Heap<T>();
for (final T element : array)
operations += heap.add(element);
for (int j = 0; j < array.length; j++) {
final Pair<T> pair = heap.remove();
array[j] = pair.value;
operations += pair.operations;
}
return operations;
}
}
/**
* This generic class performs an insertion sort.
*/
class InsertionSort<T extends Comparable<T>> implements Sorter<T> {
/**
* Sorts an array using insertion sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
int operations = 0;
for (int i = 0; i < array.length; i++)
for (int j = 0; j < i; j++) {
operations++;
if (array[j].compareTo(array[i]) > 0) {
final T temp = array[i];
for (int k = i; k > j; k--)
array[k] = array[k - 1];
array[j] = temp;
}
}
return operations;
}
}
/**
* This class performs a merge sort.
*/
class MergeSort<T extends Comparable<T>> implements Sorter<T> {
/** A temporary array used while merging the sorted elements. */
private T[] myBuffer;
/**
* This method merges two ranges of values in the array, each sorted. The
* largest index of the first range is smaller than the smallest index of
* the second range.
*
* @param array
* The array.
* @param start
* The first index (inclusive) for the first range.
* @param mid
* The first index (inclusive) for the second range.
* @param end
* The last index (exclusive) for the second range.
*
* @return The number of operations performed.
*/
private int merge(final T[] array, final int start, final int mid,
final int end) {
assert array != null;
assert start >= 0;
assert start < mid;
assert mid < end;
assert end <= array.length;
int operations = 0;
int i = 0;
int i1 = start;
int i2 = mid;
while (i1 < mid && i2 < end) {
operations++;
if (array[i1].compareTo(array[i2]) < 0)
this.myBuffer[i++] = array[i1++];
else
this.myBuffer[i++] = array[i2++];
}
if (i1 < mid) {
operations += mid - i1;
System.arraycopy(array, i1, this.myBuffer, i, mid - i1);
}
if (i2 < end) {
operations += end - i2;
System.arraycopy(array, i2, this.myBuffer, i, end - i2);
}
operations += end - start;
System.arraycopy(this.myBuffer, 0, array, start, end - start);
return operations;
}
/**
* This method performs the merge sort recursively.
*
* @param array
* The array.
* @param start
* The start index (inclusive).
* @param end
* The end index (exclusive).
*
* @return The number of operations performed.
*/
private int mergeSort(final T[] array, final int start, final int end) {
assert array != null;
assert start >= 0;
assert start < end;
assert end <= array.length;
if (start + 1 == end)
return 1;
int operations = 0;
final int mid = (start + end) / 2;
operations += this.mergeSort(array, start, mid);
operations += this.mergeSort(array, mid, end);
operations += this.merge(array, start, mid, end);
return operations;
}
/**
* Sorts an array using merge sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
// Handle a special case: when the array has no items in it.
if (array.length == 0)
return 0;
// Make a copy of the array. It's used as a temporary array while
// merging the sorted elements.
this.myBuffer = array.clone();
try {
return this.mergeSort(array, 0, array.length);
} finally {
this.myBuffer = null;
}
}
}
/**
* A generic class that contains a generic value and a recorded number of
* operations.
*/
class Pair<T> {
/** The number of operations performed. */
public final int operations;
/** A value. */
public final T value;
/**
* Initializes a new instance of the Pair class.
*
* @param value
* A value.
* @param operations
* The number of operations performed.
*/
public Pair(final T value, final int operations) {
this.value = value;
this.operations = operations;
}
}
/**
* This class performs a quick sort.
*/
class QuickSort<T extends Comparable<T>> implements Sorter<T> {
/** A random number generator used to calculate random mid-points. */
private static final Random random = new Random();
/**
* Sorts an array using quick sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
return this.quickSort(array, 0, array.length - 1);
}
/**
* This method generates a random number
*
* @param start
* The lower bound.
* @param end
* The upper bound.
*
* @return The random number generated.
*/
private int randInt(final int start, final int end) {
return start + random.nextInt(end - start);
}
/**
* This method performs the quick sort recursively.
*
* @param array
* The array.
* @param start
* The start index (inclusive).
* @param end
* The end index (inclusive).
*
* @return The number of operations performed.
*/
private int quickSort(final T[] array, final int start, final int end) {
if (start >= end)
return 0;
int mid = start;
ChengJadeSort.swap(array, start, this.randInt(start, end));
for (int i = start + 1; i <= end; i++)
if (array[i].compareTo(array[start]) < 0)
ChengJadeSort.swap(array, ++mid, i);
ChengJadeSort.swap(array, start, mid);
int operations = end - start;
operations += this.quickSort(array, start, mid - 1);
operations += this.quickSort(array, mid + 1, end);
return operations;
}
}
/**
* This class performs a selection sort.
*/
class SelectionSort<T extends Comparable<T>> implements Sorter<T> {
/**
* Sorts an array using selection sort.
*
* @param array
* The array.
*
* @return The number of operations performed.
*/
public int sort(final T[] array) {
if (array == null)
throw new NullPointerException("array");
int operations = 0;
for (int i = 0; i < array.length; i++) {
T smallest = array[i];
int smallestIndex = i;
for (int j = i; j < array.length; j++) {
operations++;
if (array[j].compareTo(smallest) < 0) {
smallest = array[j];
smallestIndex = j;
}
}
for (int k = smallestIndex; k > i; k--) {
operations++;
array[k] = array[k - 1];
}
array[i] = smallest;
}
return operations;
}
}
/**
* The interface to an object that sorts an array of values.
*/
interface Sorter<T extends Comparable<T>> {
/**
* Sorts an array.
*
* @param array
* The array to sort.
*
* @return The number of operations performed.
*/
int sort(final T[] array);
}
