삽입 정렬
삽입 정렬은 대부분의 사람이 손에 든 카드를 정리하는 방법입니다. 다음 카드를 집어, 이미 순서대로 놓인 카드 사이의 알맞은 자리에 끼워 넣습니다. 길고 무작위인 목록에서는 느리지만, 짧거나 거의 정렬된 목록에서는 매우 빨라서 실제 정렬 라이브러리에서도 여전히 쓰입니다.
기본 아이디어
목록의 앞쪽을 정렬된 상태로 유지합니다. 처음에는 첫 번째 값만이 정렬된 부분입니다. 다음 값을 꺼내 바로 앞의 값과 비교합니다. 앞의 값이 더 크면 교환하고, 한 칸 앞에서 다시 비교합니다. 앞의 값이 더 크지 않거나 값이 맨 앞에 닿으면 멈춥니다. 정렬된 부분이 하나 늘었습니다. 끝까지 모든 값에 대해 반복합니다.
예시
5, 1, 4, 2, 8을 예로 들어 봅시다. 1번째 패스는 1을 꺼냅니다. 5가 더 크므로 교환하고, 1이 맨 앞에 닿습니다: 1, 5, 4, 2, 8. 2번째 패스는 4를 꺼내 5와 교환한 뒤 1에서 멈춥니다: 1, 4, 5, 2, 8. 3번째 패스는 2를 꺼내 5, 4와 차례로 교환한 뒤 1에서 멈춥니다: 1, 2, 4, 5, 8. 4번째 패스는 8을 꺼내는데, 이미 5보다 크므로 비교 한 번이면 됩니다. 모두 비교 7번, 교환 4번입니다. 같은 목록에서 버블 정렬은 비교가 9번, 선택 정렬은 10번 필요합니다.
교환 횟수 = 역순쌍 개수
역순쌍은 순서가 잘못된 두 값의 쌍입니다. 순서가 뒤바뀐 이웃 두 값을 교환하면 역순쌍이 정확히 하나 없어지는데, 삽입 정렬은 이런 이웃만 교환합니다. 그래서 교환 횟수는 시작 목록의 역순쌍 개수와 정확히 같고, 버블 정렬과도 같습니다. 또 각 패스에는 교환으로 이어지지 않는 비교, 즉 패스를 멈추는 비교가 최대 한 번 있습니다. 따라서 비교 횟수는 역순쌍 개수에 최대 n − 1을 더한 값입니다.
적응형: 거의 정렬된 목록에서 빠름
작업량이 역순쌍 개수에 약 n을 더한 값이므로, 역순쌍이 적으면 삽입 정렬은 빠릅니다. 정렬된 목록은 비교 n − 1번에 교환이 없습니다. 모든 값이 제자리에서 몇 칸만 떨어진 목록은 n에 가까운 시간이 걸립니다. 역순쌍이 n(n − 1)/2개인 역순 목록처럼 정렬과 거리가 먼 목록만 n²에 비례하는 시간이 걸립니다. 무작위 목록에서는 평균 약 n²/4번 교환합니다.
쓰이는 곳
삽입 정렬은 안정적이고, 추가 메모리가 필요 없으며, 부가 비용도 매우 적습니다. 짧은 목록에서는 이론상 더 빠른 알고리즘보다 빠릅니다. Python과 Java의 Timsort, C++에서 쓰는 introsort 같은 여러 라이브러리 정렬은 목록의 작은 조각(보통 수십 개 이하)을 처리할 때 삽입 정렬로 바꿉니다. 값이 하나씩 들어오는 데이터에도 알맞습니다. 새 값이 들어오는 즉시 삽입할 수 있기 때문입니다.
직접 해 보기
앱을 열고 ‘재생’을 누르거나, ‘단계’를 눌러 비교를 하나씩 진행하세요. 삽입 중인 값은 고유한 색으로, 비교 대상 값은 강조 표시로 나타나고, 정렬된 부분은 초록색입니다. 버블 정렬이나 선택 정렬과 달리 초록색 부분은 확정이 아닙니다. 나중에 오는 더 작은 값이 그 안으로 들어올 수 있습니다. 거의 정렬된 목록으로 패스가 얼마나 짧은지 본 다음, 역순 목록도 시험해 보세요.
자주 묻는 질문
삽입 정렬의 시간 복잡도는?
최악과 평균의 경우 O(n²), 최선의 경우(이미 정렬된 목록) O(n)입니다. 더 정확히는 n에 역순쌍 개수를 더한 값에 비례하는 시간이 걸립니다. 추가 메모리는 O(1)만 필요합니다.
삽입 정렬과 선택 정렬은 무엇이 다른가요?
선택 정렬은 정렬되지 않은 부분 전체를 훑어 가장 작은 값을 찾으므로, 비교는 항상 n(n − 1)/2번이지만 교환은 적습니다. 삽입 정렬은 다음 값을 차례로 꺼내 필요한 만큼만 앞으로 옮기므로, 비교는 적고(특히 거의 정렬된 목록에서) 교환은 많습니다.
이진 삽입 정렬이란?
정렬된 부분에서 이진 탐색으로 새 값이 들어갈 자리를 찾는 방식으로, 비교가 최대 n번이 아니라 약 log n번으로 줄어듭니다. 하지만 자리를 만들려면 여전히 값을 밀어야 하므로, 이동 횟수와 O(n²)인 최악의 경우는 그대로입니다.
삽입 정렬은 안정 정렬인가요?
네. 값은 자신보다 엄격히 큰 값만 지나 앞으로 이동하므로, 같은 값은 원래 순서를 유지합니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
삽입 정렬 해 보기