Monday, March 6, 2017

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