Insertion Sort

Source:

public class InsertionSort {
 
   public static void main(String args[]) {
      int[] array = {9,7,5,3,1,8,6,4,2,0};
 
      System.out.print("Before:  " );
      for(int x: array) { 
         System.out.print(x + " ");
      }
      System.out.println(" ");
 
      int tmp;
      for (int i = 1; i < array.length; i++) {
         for(int j = i ; j > 0 ; j--) {
            if(array[j] < array[j-1]) {
               tmp = array[j];
               array[j] = array[j-1];
               array[j-1] = tmp;
            }
         }
         System.out.print("pass " + i + ":  " );
         for(int x: array) {
            System.out.print(x + " ");
         }
         System.out.println(" ");
      }
      System.out.println("Done");
   }
}

Output:

   # java InsertionSort 
   Before:  9 7 5 3 1 8 6 4 2 0  
   pass 1:  7 9 5 3 1 8 6 4 2 0  
   pass 2:  5 7 9 3 1 8 6 4 2 0  
   pass 3:  3 5 7 9 1 8 6 4 2 0  
   pass 4:  1 3 5 7 9 8 6 4 2 0  
   pass 5:  1 3 5 7 8 9 6 4 2 0  
   pass 6:  1 3 5 6 7 8 9 4 2 0  
   pass 7:  1 3 4 5 6 7 8 9 2 0  
   pass 8:  1 2 3 4 5 6 7 8 9 0  
   pass 9:  0 1 2 3 4 5 6 7 8 9  
   Done