삽입 정렬

정렬된 부분에 새 원소를 올바른 위치에 삽입하며 확장하는 정렬입니다.

동작 과정

[5, 3, 8, 1, 2]

i=1: [5] | 3 → 3<5, 앞으로   → [3, 5, 8, 1, 2]
i=2: [3,5] | 8 → 제자리      → [3, 5, 8, 1, 2]
i=3: [3,5,8] | 1 → 맨 앞으로 → [1, 3, 5, 8, 2]
i=4: [1,3,5,8] | 2 → 3 앞으로 → [1, 2, 3, 5, 8]

구현

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

복잡도

• 안정 정렬 O
• in-place O
• 거의 정렬된 데이터에서 매우 빠름 → 팀소트가 내부적으로 활용

→ 정렬