/*
 * @(#)InsertionSortAlgorithm.java      1.0 99/09/19
 *
 */

public class InsertionSortAlgorithm extends SortAlgorithm {
 /****                         
  * A very simple and badly documented insertion sort algorithm
  * selects the minimum and swaps position with it.
  * (I know, usually InsertionSort does not write back to the same array,
  *  but here it is required to be an in-place algorithm)
  * 
  * Oliver M"oller Sept. 1999
  ************************/

   private void swap(int[] a, int i, int j){
     int T = a[i];
     a[i] = a[j];
     a[j] = T;
   }

   public void sort(int a[]) throws Exception{
       int min;
       for(int ii=0; ii < a.length; ii++){
	   min = ii;
	   for(int jj=ii+1; jj < a.length; jj++){
	       ncmp_count++;
	       if (a[jj] < a[min])
		   min = jj;
		   pause(ii,jj);
	       if(stopRequested)return;}
	   if(min > ii)
	       swap(a,min,ii);
       }
       finished = true;
       pause();
    }
}