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.

Screen Shot 2018-01-28 at 11.49.13 AM

/**
 * 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);
	}
}

Quicksort

Hello! Below is my attempt at a quicksort. Sorters are really interesting code because they can be done in so many different ways, which can make such a difference in the speed an array is sorted. Here (No longer online :(, here’s another) is a visual example from my old professor Adam Smith. From this visual guide, you’re able to see when quicksort is most and least effective. Here’s some output:

Screen Shot 2018-02-02 at 12.00.27 PMScreen Shot 2018-02-02 at 12.01.15 PM

//
//  Quicksort2.cpp
//
//  Sorter which will sort array of random values in the "quicksort" style.
//
//  Created by Aidan Takami on 2/1/18.
//  Copyright © 2018 Aidan Takami. All rights reserved.
//


/*
     Must include iostream, cstdlib, and ctime. Site keeps deleting
     these libraries thinking they are HTML tags
/*
#include 
#include 
#include 



using namespace std;

void printArray(int r[]);
void switchValues(int r[], int, int);
void randmoArray(int r[]);
void quickSort(int r[], int, int);

//Declares the array to be sorted, as well as the const to represent the size of the array
int r[100];
const int SIZE = (sizeof(r)/4);


//Method to print out values of the array
void printArray(int r[])
{
    int i=0;
    while(i<SIZE){
        cout<<r[i]<<",";
        i++;
    }
}


//Method to swap the values at the locations of the 2 int args, within the array provided
void switchValues(int r[],int leftSide, int rightSide){
    int temp = r[leftSide];
    r[leftSide] = r[rightSide];
    r[rightSide] = temp;
}

//Method which will randomize an array of the size of the const int SIZE
void randomArray(int r[]){
    
    for(int rep = 0; rep < SIZE; rep++){
        
        r[rep] = int (rand()%100);
    }
}


//Quicksort method
void quicksort(int r[], int leftSide, int rightSide){
    
    int leftTemp = leftSide;
    int rightTemp = rightSide;
    int pivot = r[(leftSide+rightSide)/2];
    
    while(leftSidepivot)
            rightTemp--;
        
        if(leftTemp<=rightTemp){
            switchValues(r, leftTemp, rightTemp);
            leftTemp++;
            rightTemp--;

        }
        else{
            if(leftSide<rightTemp)
                quicksort(r, leftSide, rightTemp);
            if(leftTemp<rightSide)
                quicksort(r,leftTemp,rightSide);
            return;
        }
    }
}


//Main method for testing the quicksort
int main() {
  
    cout << "Generating random array!" << endl;
    randomArray(r);
    
    cout << "The unsorted array: ";
    printArray(r);
    
    cout << endl << endl;
    cout << "Sorting in progress..." << endl;
    const clock_t beginTime = clock();
    quicksort(r, 0, SIZE);
    float totalTime = ( clock () - beginTime ) /  CLOCKS_PER_SEC;
    
    cout << "The sorted array: ";
    printArray(r);
    cout << endl;
    
    cout << "The sort took " << totalTime << " milliseconds!" << endl;
    
    return 0;
}