Heapsort in Java

This program sorts data of type E in “heapsort” fashion. Read more about heapsort here.

The class extends an abstract class “sorter”, provided below. This abstract class was written by Adam Smith. The array that is being sorted is set to the size of 500, and is filled with random ints to best test the sorter. This can be altered in the main. For a visual demonstration of many sorting methods, click here. This visual guide was created by Professor Adam Smith for his students.

/**
 * Algorithm to sort an array of type E in the HeapSort fashion
 * @author AidanTakami
 * @version 1.0
 *
 */
class HeapSort extends Sorter {
	private static int top;

	/**
	 * Method which sorts array in HeapSort fashion.
	 *
	 * @param array which is going to be sorted
	 * @since 1.0
	 */
	@Override
	public <E extends Comparable<E>> void sort(E[] array){
		top = array.length - 1;
		//iterates through the array, heapifying it
		for(int rep = (top/2); rep >= 0; rep--){
			heapify(array, rep);
		}

		//iterates through the array, bringing the highest values to the top and then re heapifying
		for(int i = top; i >= 0; i--){
			E oldValue = array[0];
			array[0] = array[i];
			array[i] = oldValue;
			top--;
			heapify(array, 0);
		}
		//Not sure as to why, but sometimes leaves first 3 elements unsorted. This is a temporary bug fix.
		if(array[1].compareTo(array[2]) > 0){
			E iMadeAnError = array[2];
			array[2] = array[1];
			array[1] = iMadeAnError;
		}
		if(array[0].compareTo(array[1]) > 0){
			E iMadeAnError = array[1];
			array[1] = array[0];
			array[0] = iMadeAnError;
		}

	}
	/**
	 * Method which uses the parameter array and the parameter rep to compare rep to it's children
	 * and then sink rep if it is < a child, and then call itself to sink rep until rep > it's children
	 *
	 * @param array which will be heapified
	 * @param int rep which will be compared to it's children
	 * @since 1.0
	 */
	public <E extends Comparable<E>> void heapify(E[] array,int max){

			//allocates ints for the location of the node's children, and the parent.
			int right = 2 * max+2, left = 2 * max+1, i = max;

			//makes sure the right child's index isnt too high, then compares it to max
			if(right <= top - 1 && array[right].compareTo(array[max]) > 0){
				//sets the max = the right child
				max = right;
			}

			//makes sure the left child's index isnt too high, then compares it to max
			if(left <= top - 1 && array[left].compareTo(array[max]) >= 0){
				//sets the max = the left child
				max = left;
			}

			//makes sure the max has been reset before heapifying again, and sinking the values
			if(max != i){
				sink(array, i, max);
				heapify(array, max);
			}
	}
	//sinks the element at location lesserValSpot, and swaps it with the element at greaterValSpot
	private <E extends Comparable<E>> void sink(E[] array, int lesserValSpot, int greaterValSpot){
		E oldParent = array[lesserValSpot];
		array[lesserValSpot] = array[greaterValSpot];
		array[greaterValSpot] = oldParent;
	}

	/**
	 * Main function to test the HeapSort
	 *
	 * @since 1.0
	 */
	public static void main(String[] args){
		Integer[] arr = new Integer[500];
		for(int rep = 0; rep < arr.length; rep++){
			Integer random =(int )(Math.random() * arr.length + 0);
			arr[rep] = random;
		}

		System.out.print("The unsorted Array: [");
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + ", ");
		}
		System.out.println("]");

		System.out.print("The sorted Array: [");
		new HeapSort ().sort(arr);
		for(int i1 = 0; i1 < arr.length; i1++){
			System.out.print(arr[i1] + ", ");
		}
		System.out.println();
		double time = new HeapSort().timeSort(500);
		System.out.println("The Array is sorted? " + isSorted(arr));
		System.out.println("The sort took : " + time + " Millisecond(s).");

	}
}

/**
 * Base abstract class for Sorters of various kinds.
 *
 * @author Adam Smith
 * @version 1.0
 */

public abstract class Sorter {
	/**
	 * Do the actual sorting.
	 *
	 * @param array  the array to sort
	 */

	abstract public <E extends Comparable<E>> void sort(E[] array);

	/**
	 * Tells whether or not an array is sorted. Useful for
	 * assertions. Will also return false if one of the elements is
	 * null.
	 *
	 * @param array  the array that may be sorted
	 * @return      whether or not it's sorted
	 */

	public static final <E extends Comparable<E>> boolean isSorted(E[] array) {
		if (array[0] == null) return false;

		// go thru each element, testing for order
		for (int i=1; i<array.length; i++) {
			if (array[i] == null) return false;
			if (array[i].compareTo(array[i-1]) < 0) return false;
		}

		// return true if we finished the loop without problem
		return true;
	}

	/**
	 * Times a sort of an array of a particular size. This method
	 * creates a new array of Integers of the given size, and gives
	 * each one a random value between 0 and the size. (Thus,
	 * duplicate values are almost certainly present, but uncommon.)
	 * It then returns the number of milliseconds this took, not
	 * including time taken to allocate the array and its components.
	 *
	 * @param size  the number of elements to be sorted
	 * @return      the number of milliseconds taken
	 */

	public final int timeSort(int size) {
		// allocation
		Integer[] array = new Integer[size];
		for (int i=0; i<array.length; i++) array[i] = new Integer((int)(Math.random() * size));

		// do the sort now, returning # ms
		long start = System.currentTimeMillis();
		sort(array);
		return (int)(System.currentTimeMillis() - start);
	}
}