HeapSort
public class HeapSort {public int[] sort(int[] a) {
sort(a, a.length-1);
return a;
}
public void sort(int[] a, int end) {
for (int i = end / 2; i >= 1; i--) {
fixHeap(a, i, end, a[i]);
}
for (int i = end; i > 0; i--) {
swap(a, 0, i);
fixHeap(a, 0, i - 1, a[0]);
}
}
private void fixHeap(int[] a, int root, int end,
int key) {
int child = 2 * root; // left child
if (child < end && a[child] < a[child + 1]) {
child++;
}
if (child <= end && key < a[child]) {
a[root] = a[child];
fixHeap(a, child, end, key);
} else {
a[root] = key;
}
}
private void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
InsertionSort
public class InsertionSort {
public int[] sort(int[] input) {
int size = input.length;
for (int i = 1; i < size; i++) {
int j = i;
int x = input[i];
while (j > 0 && input[j - 1] > x) {
input[j] = input[j - 1];
j--;
}
input[j] = x;
}
return input;
}
}
MergeSort
public class MergeSort {public int[] sort(int[] list) {
mergeSort(list, 0, list.length-1);
return list;
}
public void mergeSort(int list[], int first, int last) {
if (first >= last) {
return;
}
int middle = (first + last) / 2;
mergeSort(list, first, middle);
mergeSort(list, middle + 1, last);
int size = (last - first) + 1;
int[] results = new int[size];
int start2 = middle + 1;
int indexC = 0;
int start1 = first;
while ((start1 <= middle) && (start2 <= last)) {
if (list[start1] < list[start2]) {
results[indexC] = list[start1];
start1++;
} else {
results[indexC] = list[start2];
start2++;
}
indexC++;
}
if (start1 <= middle) {
for (int i = start1; i <= middle; i++) {
results[indexC] = list[i];
indexC++;
}
} else {
for (int j = start2; j <= last; j++) {
results[indexC] = list[j];
indexC++;
}
}
int c = 0;
for (int index = first; index <= last; index++) {
list[index] = results[c];
c++;
}
}
}
QuickSort
public class QuickSort {public int[] sort(int[] list) {
quickSort(0, list.length - 1, list);
return list;
}
public void quickSort(int start, int end, int[] list) {
if (start >= end) return;
int p = partition(start, end, list);
quickSort(start, p, list);
quickSort(p + 1, end, list);
}
private int partition(int start, int end, int[] list) {
// First element
int pivot = list[start];
int pivotPoint = start;
for (int index = start + 1; index <= end; index++) {
if (list[index] < pivot) {
pivotPoint = pivotPoint + 1;
swap(pivotPoint, index, list);
}
}
swap(start, pivotPoint, list);
return pivotPoint;
}
private void swap(int i, int j, int[] list) {
int temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
SelectionSort
public class SelectionSort {public int[] sort(int[] input) {
int size = input.length;
for (int i = 0; i < size; i++) {
int index = i;
int currentMin = input[i];
for (int j = i+1; j < size; j++) {
int y = input[j];
if (y < currentMin) {
currentMin = y;
index = j;
}
}
int x = input[i];
input[i] = input[index];
input[index] = x;
}
return input;
}
}
ShellSort
public class ShellSort {public int[] sort(int[] a) {
double passes = Math.floor(Math.log(a.length));
while (passes > 1) {
int increment = (int) (Math.pow(2, passes) - 1);
for (int start = 0; start < increment; start++) {
insertSort(start, increment, a);
}
passes = passes -1;
}
insertSort(0, 1, a);
return a;
}
public void insertSort(int start, int increment, int[] a) {
int j, k, temp;
for (int i = start + increment; i < a.length; i += increment) {
j = i;
k = j - increment;
if (a[j] < a[k]) {
temp = a[j];
do {
a[j] = a[k];
j = k;
k = j - increment;
} while (j != start && a[k] > temp);
a[j] = temp;
}
}
}
}
