[알고리즘] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)란?

• 현재 위치의 값과 나머지 값들과 비교하여 알맞은 자리를 찾는 알고리즘입니다.

삽입 정렬 동작 방식

• 삽입 정렬은 현재 인덱스와 이전의 인덱스들과 비교를 하여 현재 인덱스 값 < 비교 인덱스 값인 경우 위치를 변경합니다.
• 삽입 정렬은 두 번째 인덱스부터 시작하며 마지막 인덱스에서 끝이납니다.

ex) int[] arr = new int[]{1, 5, 30, 9, 7}을 삽입 정렬방식을 적용합니다.

1. 두 번째 인덱스의 값인 5와 첫번째 인덱스 값인 1을 비교하여 두 번째 인덱스가 더 작은 경우 첫 번째 인덱스와 위치를 변경합니다.
   1 < 5 이므로 두 번째 인덱스와 첫 번째 인덱스의 값은 변경되지 않습니다.

-> {1, 5, 30, 9, 7}

2. 세 번째 인덱스의 값인 30과 두 번째 인덱스 값인 5를 비교하여 세 번째 인덱스가 더 작은 경우 두 번째 인덱스와 위치를 변경합니다.
   5 < 30 이므로 세 번째 인덱스와 두 번째 인덱스의 값은 변경되지 않습니다.

-> {1, 5, 30, 9, 7}

3. 세 번째 인덱스 값과 두 번째 인덱스 값을 비교하여 변경되지 않았고 이전의 인덱스 값들은 정렬되었으므로 이전의 인덱스들과 비교하지 않습니다.

4. 네 번째 인덱스의 값인 9와 세 번째 인덱스 값인 30을 비교하여 네 번째 인덱스가 더 작은 경우 세 번째 인덱스와 위치를 변경합니다.
   9 < 30 이므로 네 번째 인덱스와 세 번째 인덱스의 값이 변경됩니다.

-> {1, 5, 9, 30, 7}

5. 세 번째 인덱스 값과 두 번째 인덱스 값을 비교하여 변경되지 않았고 이전의 인덱스 값들은 정렬되었으므로 이전의 인덱스들과 비교하지 않습니다.

6. 다섯 번째 인덱스의 값인 7과 네 번째 인덱스 값인 30을 비교하여 다섯 번째 인덱스가 더 작은 경우 네 번째 인덱스와 위치를 변경합니다.
   7 < 30 이므로 다섯 번째 인덱스와 네 번째 인덱스의 값이 변경됩니다.

-> {1, 5, 9, 7, 30}

8. 네 번째 인덱스의 값인 7과 세 번째 인덱스 값인 9를 비교하여 네 번째 인덱스가 더 작은 경우 세 번째 인덱스와 위치를 변경합니다.
   7 < 9 이므로 네 번째 인덱스와 세 번째 인덱스의 값이 변경됩니다.

-> {1, 5, 7, 9, 30}

9. 세 번째 인덱스 값과 두 번째 인덱스 값을 비교하여 변경되지 않았고 이전의 인덱스 값들은 정렬되었으므로 이전의 인덱스들과 비교하지 않습니다.

10. 마지막 인덱스까지 모두 비교하였으므로 정렬된 값을 반환합니다.

Java 삽입 정렬 코드

    @Test
    public void sortTest(){
        int[] arr = new int[]{1, 10, 9, 5, 8, 3, 7};

        System.out.println("===== 정렬 이전 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
        System.out.println();

        insertionSort(arr);

        System.out.println("===== 정렬 이후 =====");
        for (int a : arr){
            System.out.print(a + " ");
        }
    }

    private void insertionSort(int[] arr) {
        for(int i=1; i<arr.length; i++){
            int index = i;

            while (index >= 1){
                if(arr[index] < arr[index-1]){
                    int tmp = arr[index];
                    arr[index] = arr[index-1];
                    arr[index-1] = tmp;
                }else{
                    break;
                }
                index--;
            }
        }
    }

결과

===== 정렬 이전 =====
1 10 9 5 8 3 7 
===== 정렬 이후 =====
1 3 5 7 8 9 10 

시간 복잡도

• 삽입 알고리즘은 최악의 경우(역으로 정렬된 경우)에는 1개, 2개 ... n-1개씩 비교하므로 시간 복잡도는 O(n^2)입니다.
• 이미 정렬된 경우는 한번씩 비교하면 되므로 시간 복잡도는 O(n)입니다.
• 시간 복잡도는 최악의 경우를 기준으로 평가하므로 O(n^2) 입니다.