import java.util.Comparator;

class BubbleSort2 {
  
  // same swap as before, only generic this time
  public static <E> void swap(E[] arr, int i, int j) {
    E temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  // Almost the same sort as before.  This one is
  // generic, but it also takes a comparator, c
  public static <E> void sort(E[] data, Comparator<E> c) {
    // does n passes; invariant: at the end of each loop,
    // the max element found is placed into "the right spot," to the
    // left of the numSorted elements of the sorted part of the array.
    for (int numSorted = 0; numSorted < data.length; numSorted++) {
        // does n-1 swaps
        for (int i = 1; i < data.length; i++) {
          if (c.compare(data[i-1], data[i]) > 0) {
            swap(data, i-1, i);
          }
        }
        // The line below shows that the biggest element
        // is in "the right spot" at the end of each iteration
        // of the outermost loop.  In other words, that the
        // loop invariant is always true.
        System.out.println("biggest is: " + data[data.length-numSorted-1]);
    }
  }
}