Sort
Last Updated: 2021-12-15
interface Sorter {
public <T extends Comparable<? super T>> void sort(T[] a);
}
Quick Sort
class QuickSorter implements Sorter {
public <T extends Comparable<? super T>> void sort(T[] a) {
sort(a, 0, a.length - 1);
}
public <T extends Comparable<? super T>> void sort(T[] a, int low, int high) {
T pivot = a[(low+high)/2];
int i = low, j = high;
while (i <= j) {
while (a[i].compareTo(pivot) < 0) i++;
while (a[j].compareTo(pivot) > 0) j--;
T tmp = a[j];
a[j--] = a[i];
a[i++] = tmp;
}
if (low < j)
sort(a, low, j);
if (i < high)
sort(a, i, high);
}
}
in python
def qsort(L):
if L == []:
return []
pivot = L[0]
return (qsort([x for x in L[1:] if x < pivot]) +
[pivot] +
qsort([x for x in L[1:] if x >= pivot]))
Heap Sort
class HeapSorter implements Sorter {
public <T extends Comparable<? super T>> void sort(T[] a) {
sort(a, 0, a.length - 1);
}
public <T extends Comparable<? super T>> void sort(T[] a, int low, int high) {
int size = a.length;
// Build Heap
for (int k = size / 2; k >= 0; k--) {
sink(a, k, size);
}
//Sort
while (size > 1) {
swap(a, 0, --size);
sink(a, 0, size);
}
}
private <T extends Comparable<? super T>> void sink(T[] a, int k, int size) {
int l = 2 * k;
int r = 2 * k + 1;
int largest;
if (l < size && a[l].compareTo(a[k]) > 0)
largest = l;
else
largest = k;
if (r < size && a[r].compareTo(a[largest]) > 0)
largest = r;
if (largest != k) {
swap(a, k, largest);
sink(a, largest, size);
}
}
private <T extends Comparable<? super T>> void swap(T[] a, int i, int j) {
T tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
insertion sort is the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the problem size is small (because it has low overhead).