[정렬] 삽입 정렬

삽입 정렬은 "이미 정렬된 구간"을 조금씩 늘려가며, 새로 들어온 값을 그 구간에서 알맞은 위치에 끼워 넣는 방식이다.
두 번째 원소부터 하나씩 뽑아 앞쪽과 비교하고, 자신보다 큰 값들을 오른쪽으로 밀어 빈자리에 삽입한다.

복잡도

최선: $O(n)$ — 거의 정렬된 배열에서 비교가 거의 발생하지 않음

평균/최악: $O(n²)$

코드

import java.util.Arrays;

public class InsertionSortExample {
    public static void solution(int[] arr) {
        // 예시: [34, 23, 5, 24, 1, 9, 12]
        System.out.println("원본 배열 : " + Arrays.toString(arr));

        for (int i = 1; i < arr.length; i++) {
            System.out.println(i + "번째 반복 : " + Arrays.toString(arr));

            int key = arr[i];  // 현재 삽입할 값
            int j = i - 1;

            // 앞쪽(정렬된 구간)에서 key보다 큰 값들을 한 칸씩 뒤로 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            // 빈 자리에 key 삽입
            arr[j + 1] = key;
        }

        System.out.println("정렬된 배열 : " + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = {34, 23, 5, 24, 1, 9, 12};
        solution(arr);
    }
}

시각화

로직

1. 첫 번째 원소는 정렬되어 있다고 가정
2. i=1부터 끝까지 순회:
   • 현재 값 key=arr[i]를 들고
   • 앞쪽j = i-1→0으로 가며 key보다 큰 원소를 한 칸씩 뒤로 민다.
   • 밀기가 끝나면 생긴 자리에 key를 삽입
3. 배열 끝까지 반복