/*
 *  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 Insertion Sort.  This
 *  is an O(n^2) sort in general.  This version is optimized to cut
 *  down the number of assignments.
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class InsertionSort {
  /**
   *  The sort operation.
   *
   *  @param a the array of <CODE>Object</CODE>s 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 = 0 ; i < a.length-1 ; ++i) {
      //  If the current item is in the right place, do nothing,
      //  otherwise percolate it to the right place.
      if (c.relation(a[i+1], a[i])) {
        //  Remember the current value, and percolate the `gap' to the
        //  right place in the sorted part of the array.
        Object temp = a[i+1] ;
        int j = i ;
        while (true) {
          //  Move the space back down the sorted part of the array by
          //  one, by copying values.  If we reach the end of the 
          //  array or find the right place, stop the loop.
          a[j+1] = a[j] ;
          if ((j == 0) || c.relation(a[j-1], temp))
            break ;
          --j ;
        }
        //  We have got the `gap' to the right place so drop in the
        //  value.
        a[j] = temp ;
      }
    }
  }
}