Heapsort Comparator
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package labthree.heapsort; | |
import java.util.Arrays; | |
import java.util.Comparator; | |
public class Driver { | |
private static long timeInitial; | |
private static long timeFinal; | |
private static long timeElapsed; | |
public static void main(String[] args) { | |
//Create comparators | |
Comparator minComp = new Lesser(); | |
Comparator maxComp = new Greater(); | |
int n; | |
for (int power = 4; power <= 10; power++) { | |
n = (int) Math.pow(2, power); | |
int[] maxArray = new int[n]; | |
for (int i = 0; i < n; i++) { | |
maxArray[i] = (int) (Math.random() * (n + 1)); | |
} | |
int[] minArray = Arrays.copyOf(maxArray, n); | |
//Sorts arrays using heapsort with comparator. Times them too. | |
System.out.println("MaxHeap Sort iteration " + power + ": " ); | |
startTimer(); | |
Heapsort.heapSort(maxArray, maxComp); | |
stopTimer(); | |
System.out.println("MinHeap Sort iteration " + power + ": " ); | |
startTimer(); | |
Heapsort.heapSort(minArray, minComp); | |
stopTimer(); | |
System.out.println("---------------------------------------\n"); | |
} | |
} | |
/** | |
* Gets an arbitrary point in time expressed in nanoseconds. | |
*/ | |
private static void startTimer() { | |
timeInitial = System.nanoTime(); | |
} | |
/** | |
* Gets an arbitrary point in time expressed in nanoseconds then calculates the time elapsed since | |
* {@link #startTimer()} was last called. | |
*/ | |
private static void stopTimer() { | |
timeFinal = System.nanoTime(); | |
System.out.println("timeInitial: " + timeFinal); | |
System.out.println("timeFinal: " + timeFinal); | |
timeElapsed = (timeFinal - timeInitial); | |
System.out.println("timeElapsed: " + timeElapsed + "\n"); | |
} | |
} | |
public class Heapsort { | |
private static int node; | |
private static int heapSize; | |
private static int left; | |
private static int right; | |
public static void heapSort(int[] array, Comparator comp) { | |
buildHeap(array, comp); | |
int temp; | |
for (int i = array.length - 1; i >= 0; i--) { | |
temp = array[0]; | |
array[0] = array[i]; | |
array[i] = temp; | |
heapSize--; | |
heapify(array, 0, comp); | |
} | |
} | |
private static void buildHeap(int[] array, Comparator comp) { | |
heapSize = array.length; | |
for (int i = (int) Math.floor((array.length) / 2) - 1; i >= 0; i--) { | |
heapify(array, i, comp); | |
} | |
} | |
private static void heapify(int[] array, int i, Comparator comp) { | |
left = getLeft(i); | |
right = getRight(i); | |
node = ((left <= heapSize - 1) && (comp.compare(array[left], array[i]) > 0)) | |
? left | |
: i; | |
if ((right <= heapSize - 1) && (comp.compare(array[right], array[node]) > 0)) { | |
node = right; | |
} | |
if (node != i) { | |
int temp = array[i]; | |
array[i] = array[node]; | |
array[node] = temp; | |
heapify(array, node, comp); | |
} | |
} | |
private static int getLeft(int i) { | |
return (i * 2); | |
} | |
private static int getRight(int i) { | |
return (i * 2 + 1); | |
} | |
private static int getParent(int i) { | |
return (int) Math.floor((i / 2)) - 1; | |
} | |
} | |
public class Lesser implements Comparator<Integer> { | |
@Override | |
public int compare(Integer i, Integer j) { | |
return (i < j) | |
? 1 | |
: -1; | |
} | |
} | |
public class Greater implements Comparator<Integer> { | |
@Override | |
public int compare(Integer i, Integer j) { | |
return (i > j) | |
? 1 | |
: -1; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment