삽입 정렬 (Insertion Sort)

선택 정렬, 거품 정렬과 더불어 대표적인 O(N^2) 정렬 알고리즘

정렬 범위를 1칸씩 확장해나가면서 새로운 값을 기존 값들과 비교하여 알맞은 자리에 삽입하는 방식

특징

선택/거품 정렬은 패스가 거듭될 수록 탐색 범위가 줄어드는 반면 점점 정렬 범위가 넓어짐

복잡도

1. 공간 복잡도 O(1)
   삽입 정렬은 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도
2. 시간 복잡도 O(N^2)
   우선 루프문을 통해 정렬 범위를 2개로 시작해서 전체로 확장해야 하기 때문에 기본적으로 O(N)을 시간을 소모
   각 패스에서 정렬 범위에 새롭게 추가된 값과 기존 값들의 대소 비교 및 자리 교대를 위해서 O(N)을 시간이 필요
   최적화를 통해 부분적으로 정렬된 배열에 대해서 성능을 대폭 개선할 수 있으며, 특히 완전히 정렬되어 있는 배열이 들어올 경우, O(N)까지도 시간 복잡도를 향상시킬 수 있음

구현

두 개의 반복문이 필요
내부 반복문에서는 정렬 범위에 새롭게 추가된 값과 기존 값들을 뒤에서부터 비교해나가면서 앞의 값이 뒤의 값보다 클 경우 자리 교대(swap)
외부 반복문에서는 정렬 범위를 2에서 N으로 확대해 나감

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            for (int i = end; i > 0; i--) {
                if (arr[i - 1] > arr[i])
                    swap(arr, i - 1, i);
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

최적화

기존에 있던 값들은 이전 패스에서 모두 정렬되었다는 점을 활용하면 불필요한 비교 작업을 제거할 수 있으므로 새롭게 추가된 값보다 작은 숫자를 만나는 최초의 순간까지만 내부 반복문을 수행하면 됨

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            int i = end;
            while (i > 0 && arr[i - 1] > arr[i]) {
                swap(arr, i - 1, i);
                i--;
            }
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

이 최적화를 적용하면, 정렬된 배열이 들어올 경우, O(N)의 시간 복잡도

추가 최적화

swap 작업없이 값들을 shift 시키는 것으로 삽입 정렬의 구현하는 경우, 앞의 값이 정렬 범위에 추가시킨 값보다 클 때 앞의 값을 뒤로 밀다가 최초로 작은 값을 만나는 순간 그 뒤에 추가된 값을 삽입

public class Insertion {
    public static void sort(int[] arr) {
        for (int end = 1; end < arr.length; end++) {
            int toInsert = arr[end];
            int i = end;
            while (i > 0 && arr[i - 1] > toInsert) {
                arr[i] = arr[i - 1];
                i--;
            }
            arr[i] = toInsert;
        }
    }
}