public class SelectionSort { public static void main(String[] args) { // Utilities SwissArmySorter<String> sorter = new SwissArmySorter<String>(); Copier<String> copier = new Copier<String>(); // Default Sequence (selected by Knuth on March 19, 1963) String[] seq = (args.length > 0) ? args : new String[] { "503", "087", "512", "061", "908", "170", "897", "275", "653", "426", "154", "509", "612", "677", "765", "703" }; // Copies of the Sequence String[] copy1 = copier.copy(seq, new String[seq.length]); String[] copy2 = copier.copy(seq, new String[seq.length]); // Swiss Army Arrays SwissArmyArray<String> seq1 = new SwissArmyArray<String>(copy1); SwissArmyArray<String> seq2 = new SwissArmyArray<String>(copy2); // Sort First Swiss Army Array sorter.simpleSelectionSort(seq1); System.out.println(seq1.getMeter().getReading()); System.out.println(seq1.toString()); // Sort Second Swiss Army Array sorter.pickySelectionSort(seq2); System.out.println(seq2.getMeter().getReading()); System.out.println(seq2.toString()); } } class SwissArmySorter<T extends Comparable<T>> { public SwissArmyArray<T> simpleSelectionSort(SwissArmyArray<T> seq) { // Swaps indiscriminately. SwissArmyIndex i = new SwissArmyIndex(seq); SwissArmyIndex j = new SwissArmyIndex(seq); for (i.set(0); !i.tooBig(); i.step()) { for (j.set(i.plus(1)); !j.tooBig(); j.step()) { if (seq.inDescendingOrder(i, j)) { seq.swap(i, j); } } } return seq; } public SwissArmyArray<T> pickySelectionSort(SwissArmyArray<T> seq) { // Swap selectively instead. (Modify the following code.) SwissArmyIndex i = new SwissArmyIndex(seq); SwissArmyIndex j = new SwissArmyIndex(seq); for (i.set(0); !i.tooBig(); i.step()) { for (j.set(i.plus(1)); !j.tooBig(); j.step()) { if (seq.inDescendingOrder(i, j)) { seq.swap(i, j); } } } return seq; } } class Converter<T> { public String toString(T[] seq) { String s = "["; for (int i = 0; i < seq.length; i++) { if (i > 0) { s += " "; } s += seq[i].toString(); } s += "]"; return s; } } class Copier<T> { public T[] copy(T[] orig, T[] copy) { int i; if (orig != null && copy != null && orig.length == copy.length) { i = orig.length; while (--i >= 0) { copy[i] = orig[i]; } } return copy; } } class Meter { private String reading = ""; public void tick(String s) { reading += s; } public String getReading() { return reading; } } interface IMeteredWithMaxIndex { Meter getMeter(); int getMaxIndex(); } class SwissArmyArray<T extends Comparable<T>> implements IMeteredWithMaxIndex { private T[] seq; private SwissArmyIndex indexReg; private T valueReg; private Converter<T> converter; private Meter meter; public SwissArmyArray(T[] array) { seq = array; converter = new Converter<T>(); meter = new Meter(); } public Meter getMeter() { return meter; } public void setStoredValue(T value) { meter.tick("W"); valueReg = value; } public T getStoredValue() { meter.tick("R"); return valueReg; } public void setStoredIndex(SwissArmyIndex i) { meter.tick("W"); SwissArmyIndex copy = new SwissArmyIndex(i); copy.set(i.get()); indexReg = copy; // Store copy of i, not i itself which may change. } public SwissArmyIndex getStoredIndex() { meter.tick("R"); return indexReg; } public T get(int i) { meter.tick("R"); return seq[i]; } public void set(int i, T value) { meter.tick("W"); seq[i] = value; } public int getMaxIndex() { meter.tick("R"); return seq.length - 1; } public int compare(int i, int j) { meter.tick("C"); return seq[i].compareTo(seq[j]); } public int compare(SwissArmyIndex i, SwissArmyIndex j) { return compare(i.get(), j.get()); } public void swap(int i, int j) { System.out.print("(" + get(i) + "," + get(j) + ") -> "); setStoredValue(get(i)); set(i, get(j)); set(j, getStoredValue()); System.out.println("(" + get(i) + "," + get(j) + ")"); } public void swap(SwissArmyIndex i, SwissArmyIndex j) { swap(i.get(), j.get()); } public boolean inDescendingOrder(int i, int j) { return compare(i, j) > 0; } public boolean inDescendingOrder(SwissArmyIndex i, SwissArmyIndex j) { return compare(i, j) > 0; } public boolean inAscendingOrder(int i, int j) { return compare(i, j) < 0; } public boolean inAscendingOrder(SwissArmyIndex i, SwissArmyIndex j) { return compare(i, j) < 0; } public String toString() { return converter.toString(seq); } } class SwissArmyIndex implements IMeteredWithMaxIndex { int i; int maxIndex; Meter meter; public SwissArmyIndex(IMeteredWithMaxIndex obj) { meter = obj.getMeter(); setMaxIndex(obj.getMaxIndex()); } public Meter getMeter() { return meter; } public void setMaxIndex(int max) { meter.tick("w"); maxIndex = max; } public int getMaxIndex() { meter.tick("r"); return maxIndex; } public boolean tooBig() { meter.tick("c"); return i > maxIndex; } public int get() { meter.tick("r"); return i; } public void set(int value) { meter.tick("w"); i = value; } public void step() { meter.tick("w"); i = this.plus(1); } public int plus(int n) { meter.tick("ra"); return i + n; } }
JDK ➲ Java Pi
bits ⇛ portable bytes
Thursday, March 16, 2017
SelectionSort
Subscribe to:
Posts (Atom)