/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  Sort an array of <CODE>Object</CODE>s using Bubble Sort.  This is
 *  an O(n^2) sort in general but, due to optimization, is extremely
 *  efficient on almost sorted data.
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class BubbleSort {
  /**
   *  The sort operation.
   *
   *  @param a the array to be sorted.
   *  @param c the <CODE>Comparator</CODE> used to compare the
   *  <CODE>Object</CODE>s during the sort process.
   */ 
  public static void sort(final Object[] a, final Comparator c) {
    for (int i = a.length-1 ; i > 0 ; --i) {
      //  Iterate from the beginning of the array to the location of
      //  interest.  Keep track of whether we make any swaps.
      boolean swapped = false ;
      for (int j = 0 ; j < i ; ++j) {
        //  Check to see if this pair of elements is in the right
        //  order.  If they are not then swap them.
        if (c.relation(a[j+1], a[j])) {
          Object temp = a[j] ;
          a[j] = a[j+1] ;
          a[j+1] = temp ;
          swapped = true ;
        }
      }
      //  If we made no swaps then the data is already sorted so
      //  terminate.
      if (! swapped)
        break ;
    }
  }
}