QConSP 2015: QuickSelect and stuff

IntComparator.java

public interface IntComparator {
    public static final IntComparator DEFAULT = new IntComparator() {
        @Override
        public boolean lesser(int a, int b) {
            return a < b;
        }
    };

    public static final IntComparator REVERSE = new IntComparator() {
        @Override
        public boolean lesser(int a, int b) {
            return a > b;
        }
    };

    boolean lesser(int a, int b);
}

IntHeapSorter.java

public class IntHeapSorter implements IntSorter {
    private final IntComparator comparator;

    public IntHeapSorter() {
        this(IntComparator.DEFAULT);
    }

    public IntHeapSorter(IntComparator comparator) {
        this.comparator = comparator;
    }

    @Override
    public void sort(int[] data) {
        sort(data, 0, data.length);
    }

    @Override
    public void sort(int[] data, int begin, int end) {
        sort(data, begin, end, end - begin);
    }

    @Override
    public void sort(int[] data, int begin, int end, int m) {
        select(data, begin, end, m);
    }

    @Override
    public void select(int[] data, int begin, int end, int m) {
        m = Math.min(m, end - begin);

        for (int i = (end - begin) / 2; i >= 1; i--) {
            bubbleDown(data, begin, end, i);
        }

        for (int i = 0; i < m; i++) {
            swap(data, end, end - 1, begin + i);
            bubbleDown(data, begin + i + 1, end, 1);
        }
    }

    private void bubbleDown(int[] data, int begin, int end, int n) {
        int c;
        int en = end - n;
        while ((c = min(data, begin, end, en, en - n, en - n + 1)) != end - n) {
            swap(data, end, end - n, c);
            en = c;
            n = end - c;
        }
    }

    private int min(int data[], int begin, int end, int i, int j, int k) {
        return less(data, begin, end, i, j) ?
                less(data, begin, end, i, k) ? i : k :
                less(data, begin, end, j, k) ? j : k;
    }

    private boolean less(int[] data, int begin, int end, int i, int j) {
        if (j < begin) return true;
        if (i < begin) return false;
        return comparator.lesser(data[i], data[j]);
    }

    private void swap(int[] data, int end, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

IntQuickSorter.java

public class IntQuickSorter implements IntSorter {
    public static final int MAX_DEPTH = 32;
    private final IntSorter heap;
    private final IntComparator comparator;

    public IntQuickSorter() {
        this(IntComparator.DEFAULT);
    }

    public IntQuickSorter(IntComparator comparator) {
        this.comparator = comparator;
        this.heap = new IntHeapSorter(comparator);
    }

    @Override
    public void sort(int[] data) {
        sort(data, 0, data.length);
    }

    @Override
    public void sort(int[] data, int begin, int end) {
        internalSort(data, begin, end, 0);
    }

    private void internalSort(int[] data, int begin, int end, int depth) {
        if (depth >= MAX_DEPTH) {
            //switch to heap sort when too deep
            heap.sort(data, begin, end);
            return;
        }
        if (begin + 1 >= end) return;

        int pivot = partition(data, begin, end, begin + (end - begin) / 2);
        internalSort(data, begin, pivot, depth + 1);
        internalSort(data, pivot + 1, end, depth + 1);
    }

    @Override
    public void sort(int[] data, int begin, int end, int m) {
        m = Math.min(m, end - begin);
        select(data, begin, end, m);
        sort(data, begin, begin + m);
    }

    @Override
    public void select(int[] data, int begin, int end, int m) {
        if (begin >= end) return;
        m = Math.min(m, end - begin);

        for (int depth = 0; depth < MAX_DEPTH; depth++) {
            int pivot = partition(data, begin, end, begin + (end - begin) / 2);
            int d = pivot - begin + 1;
            if (d == m) {
                return;
            } else if (m < d) {
                end = pivot;
            } else {
                m -= d;
                begin = pivot + 1;
            }
        }

        //fall back to heap sort when too deep
        heap.select(data, begin, end, m);
    }

    private int partition(int[] data, int begin, int end, int pivot) {
        int pivotValue = data[pivot];
        swap(data, pivot, end - 1);

        pivot = begin;
        for (int i = begin; i < end - 1; i++)
            if (comparator.lesser(data[i], pivotValue))
                swap(data, pivot++, i);

        swap(data, end - 1, pivot);
        return pivot;
    }

    private void swap(int[] data, int i, int j) {
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}

IntSorter.java

public interface IntSorter {
    void sort(int[] data);
    void sort(int[] data, int begin, int end);
    void sort(int[] data, int begin, int end, int m);
    void select(int[] data, int begin, int end, int m);
}