Insert Sort

1 for j D 2 to A:length 2 key D AOEj 3 // Insert AOEj into the sorted sequence AOE1 : : j 1 . 4 i D j 1 5 while i > 0 and AOEi > key 6 AOEi C 1 D AOEi 7 i D i 1 8 AOEi C 1 D key

package com.webspherenotes.algo;

public class InsertSort {

  /**
   * @param args
   */
  public static void main(String[] args) {
    int[] input = {1,2,3,4,5,6};
    
    InsertSort insertSort = new InsertSort();
    insertSort.printArray(input);
    int[] ouptut = insertSort.sort(input);
    
    System.out.print("Result is ->");
    insertSort.printArray(ouptut);
    System.out.println("Number of exchagnes " + insertSort.noOfExchanges);
  }

  
  private int[] sort(int[] input){
    int length = input.length;
    for(int i = 1 ; i < length; i++){
      int currValue = input[i];

      int exchangeStartIndex = i -1;
      while(exchangeStartIndex >=0 && currValue < input[exchangeStartIndex]){
        exchange(input, exchangeStartIndex+1, exchangeStartIndex);
        exchangeStartIndex --;
        printArray(input);
      }
    }
    return input;
  }
  
  private void printArray(int[] input){
    
    System.out.print("{");
    for(int i = 0 ; i < input.length; i++){
      System.out.print(input[i]);
      if(i != input.length -1)
        System.out.print(" , ");
    }
    System.out.println("}");
  }
  int noOfExchanges;
  private void exchange(int[] array, int first, int second){
    int temp = array[first];
    array[first] = array[second];
    array[second] = temp;
    noOfExchanges++;
  }
}