package util.jgp.algorithm; import util.jgp.interfaces.RandomAccessable; import util.jgp.predicate.BinaryPredicate; public class QuickSorter { static final int THRESHOLD = 50; private RandomAccessable vec = null; private BinaryPredicate lessThan = null; private InsertionSorter sorter = null; public QuickSorter(RandomAccessable v, BinaryPredicate less) { vec = v; lessThan = less; sorter = new InsertionSorter(v, less); } public void sort(int first, int last) { if (Math.abs(last - first) < THRESHOLD) { sorter.sort(first, last); return; } int i = first; int j = last; Object mid = vec.getElementAt(first); do { while (lessThan.execute(vec.getElementAt(i), mid)) ++i; while (lessThan.execute(mid, vec.getElementAt(j))) --j; if (i <= j) { Object tmp = vec.getElementAt(i); vec.setElementAt(i, vec.getElementAt(j)); vec.setElementAt(j, tmp); ++i; --j; } } while (i <= j); if (first < j) sort(first, j); if (i < last) sort(i, last); } public void sort() { int last = vec.getSize() - 1; if (0 < last) sort(0, last); } }