package util.jgp.algorithm; import util.jgp.interfaces.QuickSortable; import util.jgp.interfaces.RandomAccessable; import util.jgp.predicate.BinaryPredicate; public class Sorter { public static void swap(QuickSortable v, int i, int j) { Object tmp = v.getElementAt(i); v.setElementAt(i, v.getElementAt(j)); v.setElementAt(j, tmp); } public static void quickSort(QuickSortable v, BinaryPredicate lessThan, int first, int last) { if (first >= last) return; int i = first; int j = last; Object mid = v.getElementAt(first); do { while (lessThan.execute(v.getElementAt(i), mid)) ++i; while (lessThan.execute(mid, v.getElementAt(j))) --j; if (i <= j) swap(v, i++, j--); } while (i <= j); quickSort(v, lessThan, first, j); quickSort(v, lessThan, i, last); } public static void quickSort(QuickSortable v, BinaryPredicate lessThan) { quickSort(v, lessThan, 0, v.getSize() - 1); } public static void orderedInsertion(RandomAccessable v, BinaryPredicate lessThan, int first, int last, Object obj) { int i; for (i = first; i < last; ++i) if (lessThan.execute(obj, v.getElementAt(i))) { int from = last - 1; int to = last; while (to > i) v.setElementAt(to--, v.getElementAt(from--)); break; } v.setElementAt(i, obj); } /* first last | | [....................] | i | [..........] | | first last */ public static void insertionSort(RandomAccessable v, BinaryPredicate lessThan, int first, int last) { for (int i = first; i <= last; ++i) orderedInsertion(v, lessThan, first, i, v.getElementAt(i)); } public static void insertionSort(RandomAccessable v, BinaryPredicate lessThan) { insertionSort(v, lessThan, 0, v.getSize() - 1); } }