insertionSort.java

void insertionSort(int[] arr){
  for(int i = 1; i < arr.length; i++) { 
    // i가 0이 아니라 1부터 시작합니다. i가 0인 loop 는 비교할 원소가 없습니다.
    int ai = arr[i]; // 정렬된 앞 배열에 삽입될 원소, 위치를 찾을 때까지 임시저장.
    int j; // 비교 연산 및 이동 연산을 한 임시 변수
    for (j = i; j > 0 && arr[j-1] > ai; j--) // 정렬된 배열에서 ai 보다 큰 값이 나올 때까지 j 감소
      arr[j] = arr[j - 1]; // 원소가 한 칸씩 우측으로 이동
    arr[j] = ai;  // 마지막으로 나온 j에 ai 를 삽입
  }
}