public class Sorts {
/*SLECTIONSORT ALGORITHM*/
//precondition: supply instantiated array of size
// many elements
public static <Type extends Comparable<? super Type>>
void selectionSort(Type[] arr, int size) {
Type temp;
int minIndex;
for (int i = 0; i < size - 1; i++) {
minIndex = i;
for (int j = i + 1; j < size; j++) {
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
//postcondition: returns parameter argument arr in
// ascending sorted order
/*BUBBLESORT ALGORITHM*/
//precondition: supply instantiated array of size
// many elements
public static <Type extends Comparable<? super Type>>
void bubbleSort(Type[] arr, int size) {
boolean done = false;
Type temp;
while(!done) {
done = true;
for (int index = 0; index < size - 1; index ++) {
if (arr[index].compareTo(arr[index + 1]) > 0) {
temp = arr[index];
arr[index] = arr[index + 1];
arr[index + 1] = temp;
done = false;
}
}
}
}
//postcondition: returns parameter argument arr in
// ascending sorted order
/*INSERTIONSORT ALGORITHM*/
//precondition: supply instantiated array of size
// many elements
public static <Type extends Comparable<? super Type>>
void insertionSort(Type[] arr, int size) {
Type save;
for (int i = 0; i < size; i++) {
save = arr[i];
int j = i;
//move elements while they are greater than
// save value
while (j > 0 && arr[j - 1].compareTo(save) > 0) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = save;
}
}
//postcondition: returns parameter argument arr
// in ascending sorted order
/*HEAPSORT ALGORITHM*/
//precondition: supply instantiated array of size
// many elements
public static <Type extends Comparable<? super Type>>
void heapSort(Type[] arr, int size) {
if (size > 0) {
Type[] temp = (Type[])new Comparable[size];
int tempLength = size;
//step 1. buildHeap
for (int index = (size / 2) - 1; index >= 0; index--) {
percolateDown(arr, size, index);
}
//step 2. sortList
for (int index = 0; index <= size - 2; index++) {
temp[index] = arr[0]; //save root to temp array
arr[0] = arr[tempLength - 1]; //put last element into root
tempLength--; //decrease array length
percolateDown(arr, tempLength, 0); //percolate root node
}
temp[size - 1] = arr[0]; //handles last element
//step 3. copyList
System.arraycopy(temp, 0, arr, 0, size);
}
}
//postcondition: returns parameter argument arr in
// ascending sorted order
//precondition: supply instantiated array of size
// any elements and index of hole to be percolated down
private static <Type extends Comparable<? super Type>>
void percolateDown(Type[] arr, int size, int x) {
int hole = x;
Type item = arr[x];
int newHole = newHole(arr, size, hole, item);
while(newHole != -1) {
arr[hole] = arr[newHole];
hole = newHole;
newHole = newHole(arr, size, hole, item);
}
arr[hole] = item;
return;
}
//postcondition: percolates down an index to
// correct location to maintain heap quality
//precondition: supply instantiated array of
// size many elements, index of current hole,
// and item to be compared against possible new holes
private static <Type extends Comparable<? super Type>>
int newHole(Type[] arr, int size, int hole, Type item) {
int newHole = -1;
//checks for children
if (2*hole + 2 < size || 2*hole + 1 < size) {
//checks for invalid right child
if (2*hole + 2 > size) {
//compare to left child
if (item.compareTo(arr[2*hole + 1]) > 0) {
//this is the new hole
hole = 2*hole + 1;
}
}
//checks for valid right child
else if (2*hole + 2 < size){
//if left is less than right
if (arr[2*hole + 1].compareTo(arr[2*hole+2]) <= 0) {
//compares left to value
if (item.compareTo(arr[2*hole + 1]) > 0) {
//this is the new hole
newHole = 2*hole + 1;
}
}
else {
//compares right child to value
if (item.compareTo(arr[2*hole + 2]) > 0) {
//this is the new hole
newHole = 2*hole + 2;
}
}
}
else {
//checks if value is greater than left child
if (item.compareTo(arr[2*hole + 1]) > 0) {
//this is the new hole
newHole = 2*hole + 1;
}
}
}
return newHole;
}
//postcondition: returns index of new hole
/*MERGESORT ALGORITHM*/
//precondition: supply instantiated array
// of size many elements
public static <Type extends Comparable<? super Type>>
void mergeSort(Type[] arr, int size) {
mergesort(arr, 0, size - 1);
}
//postcondition: returns parameter argument
// arr in ascending sorted order
//precondition: supply instantiated array of
// size many elements, index of first element,
// and index of last element
private static <Type extends Comparable<? super Type>>
void mergesort(Type[] arr, int first, int last) {
if (first < last) {
int middle = (first + last) / 2;
//recursive mergesort on first half
mergesort(arr, first, middle);
//recursive mergesort on second half
mergesort(arr, middle + 1, last);
//merge both halves
mergeSortedHalves(arr, first, middle, last);
}
}
//postcondition: returns parameter argument
// array in ascending sorted order
//precondition: supply instantiated array,
// index of left element, index of middle
// element, and index of right element
private static <Type extends Comparable<? super Type>>
void mergeSortedHalves(Type[] arr, int left, int middle, int right) {
Type[] temp = (Type[])new Comparable[right - left + 1];
int index1 = left;
int index2 = middle + 1;
int index = 0;
//while both halves have elements
while (index1 <= middle && index2 <= right) {
if (arr[index1].compareTo(arr[index2]) <= 0) {
temp[index] = arr[index1];
index1++;
}
else {
temp[index] = arr[index2];
index2++;
}
index++;
}
//if upper while loop finished but first half
// has more elements
if (index1 <= middle) {
while (index1 <= middle) {
temp[index] = arr[index1];
index++;
index1++;
}
}
//if upper while loop finished but second half
// has more elements
else if (index2 <= right) {
while (index2 <= right) {
temp[index] = arr[index2];
index++;
index2++;
}
}
System.arraycopy(temp, 0, arr, left, temp.length);
}
//postcondition: returns a single sorted array from
// sub array[left to middle] and sub array[middle to right]
/*QUICKSORT ALGORITHM*/
//precondition: supply instantiated array of
// size many elements
public static <Type extends Comparable<? super Type>>
void quickSort(Type[] arr, int size) {
quickSort(arr, 0, size - 1);
}
//postcondition: returns parameter argument array
// in ascending sorted order
//precondition: supply instantiated array,
// index of first element, and index of last element
private static <Type extends Comparable<? super Type>>
void quickSort(Type[] arr, int first, int last) {
if (first < last) {
setPivotToEnd(arr, first, last);
int pivotIndex = splitList(arr, first, last);
quickSort(arr, first, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, last);
}
}
//postcondition: returns parameter argument array
// in ascending sorted order
//precondition: supply instantiated array, index
// of left element, and index of right element
private static <Type extends Comparable<? super Type>>
void setPivotToEnd(Type[] arr, int left, int right) {
int center = (left + right) / 2;
Type temp;
if (arr[center].compareTo(arr[left]) < 0) {
temp = arr[center];
arr[center] = arr[left];
arr[left] = temp;
}
if (arr[right].compareTo(arr[left]) < 0) {
temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
if (arr[center].compareTo(arr[right]) < 0) {
temp = arr[center];
arr[center] = arr[right];
arr[right] = temp;
}
}
//postcondition: median of three values at left,
// right, and center is swapped to right index
//precondition: supply instantiated array, index
// of left element, and index of right element
private static <Type extends Comparable<? super Type>>
int splitList(Type[] arr, int left, int right) {
int indexL = left;
int indexR = right - 1;
Type pivot = arr[right];
Type temp;
while (indexL <= indexR) {
//while indices have not run over
while (arr[indexL].compareTo(pivot) < 0) {
//find element greater than pivot
indexL++;
}
while (indexL <= indexR && arr[indexR].compareTo(pivot) > 0) {
//find element less than pivot
indexR--;
}
if (indexL <= indexR) {
//swap the two values
temp = arr[indexL];
arr[indexL] = arr[indexR];
arr[indexR] = temp;
indexL++;
indexR--;
}
}
//if indexL is not the right index swap them
if (indexL != right) {
temp = arr[indexL];
arr[indexL] = arr[right];
arr[right] = temp;
}
return indexL;
}
//postcondition: returns index of final pivot position
}