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).