import java.util.Comparator;
import structure5.*;

class BubbleSort {
  
  /**
   * Swaps the two elements in arr at index i and at index j.
   * @param arr A vector of type E.
   * @param i a valid index into arr.
   * @param j another valid index into arr.
   * @return Nothing, except that the two elements are swapped in-place.
   */
  public static <E> void swap(Vector<E> arr, int i, int j) {
    E temp = arr.get(i);
    arr.set(i, arr.get(j));
    arr.set(j, temp);
  }

  /**
   * A sort method that performs an in-place comparison sort (bubble sort).
   * @param data A vector containing data of type E.
   * @param c A comparator for type E.
   * @return Nothing, except that data is sorted in-place.
   */
  public static <E> void sort(Vector<E> data, Comparator<E> c) {
    for (int numSorted = 0; numSorted < data.size(); numSorted++) {
      for (int i = 1; i < data.size(); i++) {
        if (c.compare(data.get(i-1), data.get(i)) > 0) {
          swap(data, i-1, i);
        }
      }
    }
  }
}