삽입 정렬 (Insertion Sort)

삽입 정렬 (Insertion Sort)

정렬된 부분에 새 요소를 올바른 위치에 삽입하는 과정을 반복하여 정렬하는 알고리즘

목적: 소규모 데이터, 거의 정렬된 데이터, 온라인 정렬

특징: 안정 정렬, 제자리, 적응적(정렬도에 따라 성능 향상), 온라인

동작: 두 번째 요소부터 시작. 현재 요소(key)를 정렬된 부분(왼쪽)에서 올바른 위치를 찾아 삽입. 정렬된 부분의 오른쪽부터 key와 비교하여 key보다 큰 요소들을 한 칸씩 오른쪽으로 이동 후 빈 자리에 key 삽입

• •예: [5,3,8,1] → key=3: [3,5,8,1] → key=8: [3,5,8,1] → key=1: [1,3,5,8]

시간 복잡도: 최선 O(n) - 이미 정렬됨, 평균·최악 O(n²)

공간 복잡도: O(1) - 제자리

장점: 단순, 안정, 적응적(거의 정렬 시 빠름), 소규모 빠름, 온라인

단점: 대규모 데이터에서 느림(O(n²))

적용사례: 소규모 데이터(<50개), 거의 정렬된 데이터, Tim Sort/Intro Sort의 하위 루틴, 온라인 정렬

비교: 삽입(적응적/안정/소규모) vs 선택(비적응적/불안정) vs 버블(느림)

연관: 정렬, 버블 정렬, Tim Sort, O(n²)