삽입 정렬(insertion sort)

• 자료 배열의모든 요소를 앞에서 부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위
  치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
• 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정 한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
• 입력 자료가 역순인 경우 최악인 O(n2)이다.
• 입력 자료가 정렬된 경우 최선으로 O(n)이다.

public class SortTest {
    @Test
    void insertion() {
        int[] array = new int[]{5,9,3,1,2,8,4,7,6};
//        int[] array = new int[]{1,2,3,4,5,6,7,8,9};
//        int[] array = new int[]{9,8,7,6,5,4,3,2,1};

        for(int i = 1 ; i < array.length ; i++){

            int temp = array[i];
            int index = i - 1;

            while( (index >= 0) && ( array[index] > temp ) ) {

                array[index + 1] = array[index];
                index--;
            }
            array[index + 1] = temp;
        }

        assertArrayEquals(array, new int[]{1,2,3,4,5,6,7,8,9});
    }
 }

시작 [5, 9, 3, 1, 2, 8, 4, 7, 6]

1. [5, 9, 3, 1, 2, 8, 4, 7, 6]
2. [3, 5, 9, 1, 2, 8, 4, 7, 6]
3. [1, 3, 5, 9, 2, 8, 4, 7, 6]
4. [1, 2, 3, 5, 9, 8, 4, 7, 6]
5. [1, 2, 3, 5, 8, 9, 4, 7, 6]
6. [1, 2, 3, 4, 5, 8, 9, 7, 6]
7. [1, 2, 3, 4, 5, 7, 8, 9, 6]
8. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [9, 8, 7, 6, 5, 4, 3, 2, 1]

1. [8, 9, 7, 6, 5, 4, 3, 2, 1]
2. [7, 8, 9, 6, 5, 4, 3, 2, 1]
3. [6, 7, 8, 9, 5, 4, 3, 2, 1]
4. [5, 6, 7, 8, 9, 4, 3, 2, 1]
5. [4, 5, 6, 7, 8, 9, 3, 2, 1]
6. [3, 4, 5, 6, 7, 8, 9, 2, 1]
7. [2, 3, 4, 5, 6, 7, 8, 9, 1]
8. [1, 2, 3, 4, 5, 6, 7, 8, 9]

시작 [1, 2, 3, 4, 5, 6, 7, 8, 9]

1. [1, 2, 3, 4, 5, 6, 7, 8, 9]