SelectionSort

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;
  }
}

BubbleSort

class Sorter<T extends Comparable<T>> {
  
  private T[] seq;
  
  private T[] sortedSeq() {
    System.out.println();
    return seq;
  }

  private void swap(int i, int j) {
    T tmp = seq[i];
    seq[i] = seq[j];
    seq[j] = tmp;
  }
  
  private boolean wereSwapped(int i, int j) {
    if (seq[i].compareTo(seq[j]) > 0) {
      swap(i, j);
      System.out.print("s");
      return true;
    }
    System.out.print(".");
    return false;
  }

  public T[] bubbleSortSilly(T[] array) {
    seq = array;
    boolean done = false;
    while (!done) {
      done = true;
      for (int i = 0; i < seq.length - 1; i++) {
        if (wereSwapped(i, i + 1)) {
          done = false;
        }
      }
    }
    return sortedSeq();
  }
  
  public T[] bubbleSort(T[] array) {
    seq = array;
    for (int j = seq.length - 1; j > 0; j--) {
      for (int i = 0; i < j; i++) {
        wereSwapped(i, i + 1);
      }
    }
    return sortedSeq();
  }
  
  public T[] bubbleSortSmart(T[] array) {
    seq = array;
    boolean done = false;
    for (int j = seq.length - 1; !done && j > 0; j--) {
      done = true;
      for (int i = 0; i < j; i++) {
        if (wereSwapped(i, i + 1)) {
          done = false;
        }
      }
    }
    return sortedSeq();
  }
  
  public T[] bubbleSortSmarter(T[] array) {
    seq = array;
    int k;
    for (int j = seq.length - 1; j > 0; j = k) {
      k = 0;
      for (int i = 0; i < j; i++) {
        if (wereSwapped(i, i + 1)) {
          k = i;
        }
      }
    }
    return sortedSeq();
  }
}

class Printer<T> {
  public void print(T[] array) {
    for (int i = 0; i < array.length; i++) {
      if (i > 0) {
        System.out.print(" ");
      }
      System.out.print(array[i]);
    }
    System.out.println();
  }
  public void println(T[] array) {
    print(array);
    System.out.println();
  }
}

class StringCopier {
  public String[] copy(String[] array) {
    int i = array.length;
    String[] copyOfArray = new String[i];
    while (--i >= 0) {
      copyOfArray[i] = array[i];
    }
    return copyOfArray;
  }
}

public class BubbleSort {
  public static void main(String[] args) {

    String[] array = (args.length > 0) ? args :
      new String[] {
        "503",
        "087",
        "512",
        "061",
        "908",
        "170",
        "897",
        "275",
        "653",
        "426",
        "154",
        "509",
        "612",
        "677",
        "765",
        "703"
      };

    StringCopier copier = new StringCopier();
    Printer<String> printer = new Printer<String>();
    Sorter<String> sorter =  new Sorter<String>();
    
    printer.println(array);
    printer.println(sorter.bubbleSortSilly(copier.copy(array)));
    printer.println(sorter.bubbleSort(copier.copy(array)));
    printer.println(sorter.bubbleSortSmart(copier.copy(array)));
    printer.println(sorter.bubbleSortSmarter(copier.copy(array)));    
  }
}

DoTheShuffle

// ===============================================================
// The modern version of the Fisher–Yates shuffle, designed for
// computer use, was introduced by Richard Durstenfeld in 1964 and
// popularized by Donald E. Knuth in The Art of Computer
// Programming as "Algorithm P". Neither Durstenfeld nor Knuth, in
// the first edition of his book, acknowledged the work of Fisher
// and Yates; they may not have been aware of it. Subsequent
// editions of The Art of Computer Programming mention Fisher and
// Yates' contribution.
//
//                              - WIKIPEDIA (Fisher–Yates shuffle)
// ===============================================================

public class DoTheShuffle {

  private static void printSeq(String[] s) {
    for (int i = 0; i < s.length; i++) {
      if (i > 0) {
        System.out.print(" ");
      }
      System.out.print(s[i]);
    }
    System.out.println();
  }

  public static void main(String[] args) {

    ISort<String> sorter;
    IShuffle<String> shuffler;

    if (args.length == 0) {
      System.out.println("crickets");
      return;
    }

    sorter = new MeteredInsertionSorter<String>();
    shuffler = new LazyStudentShuffler<String>();

    // Original
    printSeq(args);

    // Sorted
    sorter.sort(args);
    printSeq(args);

    // Shuffled
    shuffler.shuffle(args);
    printSeq(args);
  }
}

LazyStudentShuffler

class LazyStudentShuffler<T>
extends Shuffler<T> {
  public void maneuver(T[] seq, int from, int to) {
  }
}

Shuffler

abstract class Shuffler<T>
implements IShuffle<T> {

  private SeqValidator<T> validator = new SeqValidator<T>();

  // IShuffle methods

  public T[] shuffle(T[] seq)
  throws IllegalArgumentException {
    validator.assertSeqNotEmpty(seq);
    maneuver(seq, 0, seq.length - 1);
    return seq;
  }

  public T[] shuffle(T[] seq, int from, int to)
  throws IndexOutOfBoundsException, IllegalArgumentException {
    validator.assertValidRange(seq, from, to);
    maneuver(seq, from, to);
    return seq;
  }

  // Abstract methods

  public abstract void maneuver(T[] seq, int from, int to);
}

IShuffle

interface IShuffle<T> {

  T[] shuffle(T[] seq)
  throws IllegalArgumentException;

  T[] shuffle(T[] seq, int from, int to)
  throws IndexOutOfBoundsException, IllegalArgumentException;
}

Snap!

SeqValidator

class SeqValidator<T> {

  private static int iMin = 0;
  private int iMax = 0;

  public void assertSeqNotEmpty(T[] seq)
  throws IllegalArgumentException {
    if (seq == null) {
      throw new IllegalArgumentException("seq cannot be null");
    }
    iMax = seq.length - 1;
    if (iMax < 0) {
      throw new IllegalArgumentException("seq cannot be empty");
    }
  }

  public void assertValidRange(T[] seq, int from, int to)
  throws IllegalArgumentException, IndexOutOfBoundsException {
    assertSeqNotEmpty(seq);
    if (from < iMin || from > iMax) {
      throw new IndexOutOfBoundsException("from is out of bounds");
    }
    if (to < iMin || to > iMax) {
      throw new IndexOutOfBoundsException("to is out of bounds");
    }
  }

}

ISort

interface ISort<T extends Comparable<T>> {

  T[] sort(T[] seq)
  throws IllegalArgumentException;

  T[] sort(T[] seq, int from, int to)
  throws IndexOutOfBoundsException, IllegalArgumentException;
}

MeteredQuickerLinearSearcher

// ===============================================================
// Look twice before you leap two steps.
// ===============================================================

class MeteredQuickerLinearSearcher<T extends Comparable<T>>
extends MeteredSearcher<T> {

  public int maneuver(T[] seq, T key, int from, int to) {

    int step = from < to ? 1 : -1;
    int leap = 2 * step;
    T bumpedValue = seq[to];
    seq[to] = key;

    int i = from;
    while (tick() && key.compareTo(seq[i]) != 0) {
      if (tick() && key.compareTo(seq[i + step]) == 0) {
        i += step;
        break;
      }
      i += leap;
      tick();
    }
    seq[to] = bumpedValue;
    return tick() && key.compareTo(seq[i]) == 0 ? i : fail;
  }
}

MeteredQuickLinearSearcher

// ===============================================================
// Put an Elephant in Cairo, to wit put the key in the last place
// you'd look.
// ===============================================================
 
class MeteredQuickLinearSearcher<T extends Comparable<T>>
extends MeteredSearcher<T> {

  public int maneuver(T[] seq, T key, int from, int to) {
 
    int step = from < to ? 1 : -1;
    T bumpedValue = seq[to];
    seq[to] = key;

    int i = from;
    while (tick() && key.compareTo(seq[i]) != 0) {
      i += step;
      tick();
    }
    seq[to] = bumpedValue;
    return tick() && key.compareTo(seq[i]) == 0 ? i : fail;
  }
}

MeteredLinearSearcher

// ===============================================================
// "BEGIN AT THE BEGINNING, and go on till you find the right key;
//  then stop."
//                 - KNUTH (The Art of Computer Programming 3 6.1)
// ===============================================================

class MeteredLinearSearcher<T extends Comparable<T>>
extends MeteredSearcher<T> {

  public int maneuver(T[] seq, T key, int from, int to) {
 
    int step = from < to ? 1 : -1;
    int i = from;

    while (tick() && i != to) {
      if (tick() && key.compareTo(seq[i]) == 0) {
        return i;
      }
      i += step;
      tick();
    }
    return tick() && key.compareTo(seq[i]) == 0 ? i : fail;
  }
}

ISearch

// ===============================================================
// God bless the day I discovered you.
//
//          - MALLETTE, MORRISON, RYAN ("Lookin' for Love" lyrics)
// ===============================================================

interface ISearch<T extends Comparable<T>> {

  /**
   * Search for key in the part of seq that is between from and
   * to inclusive. Return the index of a position in seq where a
   * value matching key was found or -1 if no such value exists
   * between from and to.
   *
   * @author  John P. Spurgeon
   *
   * @param   seq   a sequence of one or more values
   * @param   key   a value to find
   * @param   from  a boundary value
   * @param   to    a boundary value
   *
   * @returns an integer between from and to inclusive or -1
   * @throws  IllegalArgumentException if seq is null or
   *          seq.length is zero
   * @throws  IndexOutOfBoundsException if either from or to is
   *          less than zero or greater than seq.length - 1
   */

  int find(T[] seq, T key, int from, int to)
  throws IndexOutOfBoundsException, IllegalArgumentException;

  int find(T[] seq, T key)
  throws IllegalArgumentException;
}

IMetered

// ===============================================================
// Algorithm M requires a fixed amount of storage, so we will
// analyze only the time required to perform it. To do this, we
// will count the number of times each step is executed.
//
//              - KNUTH (The Art of Computer Programming 1 1.2.10)
// ===============================================================

interface IMetered {
  boolean tick();
  long unitsCounted();
  long timeConsumed();
}

MeteredSorter

abstract class MeteredSorter<T extends Comparable<T>>
extends Sorter<T> implements IMetered {

  private Meter meter;
  private long startReading, endReading;
  private long startTime, endTime;

  // Constructors

  public MeteredSorter() {
    meter = new Meter();
  }
  public MeteredSorter(Meter m) {
    meter = m;
  }

  // Private metering methods

  private void startMetering() {
    startReading = meter.reading();
    startTime = System.nanoTime();
  }
  private void stopMetering() {
    endTime = System.nanoTime();
    endReading = meter.reading();
  }

  // IMetered methods

  public boolean tick() {
    meter.tick();
    return true;
  }
  public long unitsCounted() {
    return endReading - startReading;
  }
  public long timeConsumed() {
    return endTime - startTime;
  }

  // ISort methods

  public T[] sort(T[] seq)
  throws IllegalArgumentException {
    startMetering();
    super.sort(seq);
    stopMetering();
    return seq;
  }

  public T[] sort(T[] seq, int from, int to)
  throws IllegalArgumentException, IndexOutOfBoundsException {
    startMetering();
    super.sort(seq, from, to);
    stopMetering();
    return seq;
  }
}

MeteredInsertionSorter

class MeteredInsertionSorter<T extends Comparable<T>>
extends MeteredSorter<T> {
  public void maneuver(T[] seq, int from, int to) {
 
    final int step = from < to ? 1 : -1;
    final int stop = to + step;
    int i, jCurr, jPrev;
    T key;

    for (i = from + step; i != stop; i += step) {
      tick();
      key = seq[i];
      for (jCurr = i; jCurr != from; jCurr = jPrev) {
        tick();
        jPrev = jCurr - step;
        if (key.compareTo(seq[jPrev]) >= 0) {
          break;
        }
        seq[jCurr] = seq[jPrev];
      }
      seq[jCurr] = key;
    }
    return;
  }
}

index	-1	0	1	2	3	4	5
seq
from
to
stop
i
jCurr
jPrev

key

step

meter

0

Sorter

abstract class Sorter<T extends Comparable<T>>
implements ISort<T> {

  private SeqValidator<T> validator = new SeqValidator<T>();

  // ISort methods

  public T[] sort(T[] seq)
  throws IllegalArgumentException {
    validator.assertSeqNotEmpty(seq);
    maneuver(seq, 0, seq.length - 1);
    return seq;
  }

  public T[] sort(T[] seq, int from, int to)
  throws IndexOutOfBoundsException, IllegalArgumentException {
    validator.assertValidRange(seq, from, to);
    maneuver(seq, from, to);
    return seq;
  }

  // Abstract methods

  public abstract void maneuver(T[] seq, int from, int to);
}

404

    while (key.compareTo(seq[i]) != 0) {
      i += step;
    }

Meter

// ===============================================================
// As commercial use of electric energy spread in the 1880s, it
// became increasingly important that an electric energy meter,
// similar to the then existing gas meters, was required to
// properly bill customers for the cost of energy, instead of
// billing for a fixed number of lamps per month.
//
//       - WIKIPEDIA (Electricity meter, retrieved on 19 Feb 2017)
// ===============================================================

class Meter {

  private long tally;

  public Meter() {
    tally = 0L;
  }
  public void tick() {
    tally += 1L;
  }
  public long reading() {
    return tally;
  }
}

Searcher

abstract class Searcher<T extends Comparable<T>>
implements ISearch<T> {

  public static int fail = -1;
  private SeqValidator<T> validator = new SeqValidator<T>();

  // ISearch methods

  public int find(T[] seq, T key)
  throws IllegalArgumentException {
    validator.assertSeqNotEmpty(seq);
    return maneuver(seq, key, 0, seq.length - 1);
  }

  public int find(T[] seq, T key, int from, int to)
  throws IllegalArgumentException, IndexOutOfBoundsException {
    validator.assertValidRange(seq, from, to);
    return maneuver(seq, key, from, to);
  }

  // Abstract methods

  public abstract int maneuver(T[] seq, T key, int from, int to);
}