삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 배열을 나누어, 정렬되지 않은 부분의 요소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘입니다.

1. 동작 원리와 루프 불변성

삽입 정렬의 핵심 아이디어는 루프 불변성(Loop Invariant)으로 설명할 수 있습니다. 길이 n인 배열 data에 대해, 인덱스 [0, i) 범위는 항상 정렬된 상태를 유지하며, 인덱스 [i, n) 범위의 원소들을 하나씩 정렬된 영역의 적절한 위치로 이동시킵니다.

오름차순 정렬을 기준으로, 현재 선택된 요소 data[i]를 정렬된 영역인 data[0...i-1]의 뒤에서부터 비교하며 앞으로 이동합니다. data[i]가 이전 요소보다 작다면 자리를 바꾸고, 크거나 같은 요소를 만나는 순간 해당 위치가 삽입될 지점이 됩니다.

선택 정렬과의 차이점

• 선택 정렬: 아직 정렬되지 않은 나머지 영역에서 최솟값을 찾아 현재 위치에 놓습니다. 한 번 결정된 위치는 최종 결과에서 변하지 않습니다.
• 삽입 정렬: 현재 요소까지의 앞부분만 정렬된 상태를 유지합니다. 새로운 요소가 삽입됨에 따라 기존에 정렬되었던 요소들의 인덱스가 뒤로 밀릴 수 있으므로, 최종 위치가 확정된 것은 아닙니다.

2. 코드 구현 및 최적화

정렬 알고리즘의 검증과 성능 측정을 위해 유틸리티 클래스를 먼저 정의합니다.

public class SortValidator {
    private SortValidator() {}

    public static <E extends Comparable<E>> boolean isSorted(E[] elements) {
        for (int i = 1; i < elements.length; i++) {
            if (elements[i - 1].compareTo(elements[i]) > 0) {
                return false;
            }
        }
        return true;
    }

    public static <E extends Comparable<E>> void measureTime(String label, E[] elements, Runnable sortTask) {
        long start = System.nanoTime();
        sortTask.run();
        long end = System.nanoTime();
        
        double duration = (end - start) / 1_000_000_000.0;
        
        if (!isSorted(elements)) {
            throw new RuntimeException(label + " 정렬 실패");
        }
        System.out.printf("%s (n=%d): %f 초%n", label, elements.length, duration);
    }
}

다음은 기본적인 스와프(Swap) 방식과 연산 횟수를 줄인 최적화 방식의 삽입 정렬 구현입니다.

public class InsertionSort {
    private InsertionSort() {}

    // 기초적인 스와프 방식
    public static <E extends Comparable<E>> void sortBasic(E[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = i; j > 0 && data[j].compareTo(data[j - 1]) < 0; j--) {
                swap(data, j, j - 1);
            }
        }
    }

    private static <E> void swap(E[] data, int i, int j) {
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    // 대입(Assignment)을 이용한 최적화 방식
    public static <E extends Comparable<E>> void sortOptimized(E[] data) {
        for (int i = 0; i < data.length; i++) {
            E target = data[i];
            int j;
            // 스와프 대신 요소를 뒤로 미는(Shifting) 방식 사용
            for (j = i; j > 0 && target.compareTo(data[j - 1]) < 0; j--) {
                data[j] = data[j - 1];
            }
            data[j] = target;
        }
    }
}

3. 알고리즘 성능 분석

삽입 정렬의 최적화 핵심은 스와프 횟수의 감소에 있습니다. 기초적인 방식은 매 비교마다 세 번의 대입이 일어나는 swap 연산을 수행하지만, 최적화된 방식은 적절한 위치를 찾을 때까지 요소를 한 칸씩 뒤로 밀고 마지막에 한 번만 대입하므로 연산 비용이 훨씬 저렴합니다.

시간 복잡도 특성

• 평균 및 최악의 경우: $O(n^2)$의 복잡도를 가집니다.
• 최선의 경우: 입력 데이터가 이미 거의 정렬되어 있는 경우, 내부 루프의 조건문이 즉시 종료되어 $O(n)$에 수렴하는 매우 빠른 속도를 보여줍니다.

이러한 특성 때문에 삽입 정렬은 선택 정렬과 달리 데이터의 초기 상태에 따라 성능 차이가 크게 발생하며, 데이터가 작거나 거의 정렬된 상태에서 매우 효율적인 알고리즘으로 평가받습니다.