insertion sort.java

import java.io.*;
import java.util.*;

/*  
 * [1, 3, 4, 5, 7, 8]
    
p  id
 * [5, 1, 4, 3, 7, 8]
      p  id
 * [1, 5, 4, 3, 7, 8]
 
 * [1, 4, 5, 3, 7, 8]
 *
 
 [2, 5, 1, 3]
 [2, 1, 5, 3]
[5,2,1]

* [1, 3, 4, 5, 7, 8]
 */

[1, 1, 3, 4, 5]

/*
input:   [5, 1, 4, 3, 7, 8]
output:  [1, 3, 4, 5, 7, 8]

input:   [-5, 0, 0, 2, -10]
output:  [-10, -5, 0, 0, 2]

input:   [1]
output:  [1]

input:   []
output:  []
*/

class Solution {
  public static void main() {
    
    int[] correctAns = Array.sort(inputArray);
    int[] mySolution = insertionSort(inputArray);
    Assertequal(correctAnsm mySolution);
    
    
//     if(inputArray == null || inputArray.size() == 0) {
//       throw new Exception e;
//     }
//     int pre = inputArray[0];
//     for(int input : inputArray) {
//       if(input < pre) {
//         throw new Exception e;
//       }
//       pre = input;
//     }
    
  }
  
//   input:   [-5, 0, 0, 2, -10]
// output:  [-10, -5, 0, 0, 2]
  
  private int[] insertionSort(int[] inputArray) {
    if(inputArray == null || inputArray.length == 0) {
        throw new Exception e;
    }
    
    int[] res = new int[inputArray.length];
    for(int id = 1, index = 0; id < inputArray.size(); i++) {
        for(int j = 0; j < id; j++) {
            if(inputArray[id] > inputArray[j]) {
                res[index++] = inputArray[j];
            } else {
                res[index++] = inputArray[id];
            }
        }
    }
    return res;
  }
  
}