/* File: NaiveInsertionSort.java - March 2013
   Based on a March 2011 version, converted 
   to implement IntSorter interface */

package l09;

/**
 * Insertion sort (maintain sorted prefix, insert each additional element)
 * 
 * In this naive version the desired position is found by a left to right 
 * scan and then the object is inserted into that position using the
 * ArrayManipulation.insert method.
 *
 * @author Michael Albert
 *
 */

public class NaiveInsertionSort implements IntSorter{


   public void sort(int[] a) {

      for(int i = 1; i < a.length; i++) {
         ArrayManipulation.insert(a, 
                                  findPosition(a, 0, i, a[i]), 0, i+1, 
                                  a[i]);
      }
   }

   public String getName() {
      return "Naive insertion sort";
   }

   public static int findPosition(int[] a, int left, int right, int value) {
     
      int i = left;
      while (i < right && a[i] < value) i++;
      return i;
   
   }
}