삽입 정렬(Insertion Sort) 완벽 이해 — 정보처리기사 자료구조 핵심 정리

💡 삽입 정렬, 카드를 손에 쥐고 정렬하듯 생각하기

삽입 정렬(Insertion Sort)은 카드 게임에서 손에 든 카드를 정렬하는 방식과 똑같습니다. 새 카드를 한 장씩 받을 때마다, 이미 손에 들고 있는 정렬된 카드 묶음 사이의 알맞은 자리를 찾아 끼워 넣습니다. 손에 든 카드 전체를 매번 다시 정렬하는 게 아니라, 새로 들어온 카드 하나만 제자리를 찾아주는 것이 핵심입니다.

배열로 옮기면 이렇게 됩니다. 배열의 왼쪽 부분은 이미 정렬이 끝난 구간이고, 오른쪽 부분은 아직 정렬되지 않은 구간입니다. 매 단계(패스, pass)마다 정렬되지 않은 구간의 맨 앞 원소를 하나 꺼내(key), 정렬된 구간을 뒤에서부터 훑으며 key보다 큰 값들을 한 칸씩 뒤로 밀어낸 다음, key보다 작거나 같은 값을 만나는 순간(또는 맨 앞에 도달하는 순간) 그 자리에 key를 삽입합니다. 이 글은 정보처리기사·산업기사 자료구조 시험에서 삽입 정렬 단독으로 나올 수 있는 회전별 추적 문제, 시간복잡도 계산 문제, 안정 정렬 여부를 묻는 문제까지 정확한 손 계산으로 파고듭니다.

💡 예제 배열로 처음부터 끝까지 직접 추적하기

예제 배열 [5, 2, 4, 6, 1, 3]을 오름차순으로 정렬한다고 가정하겠습니다. 원소가 6개이므로 삽입 정렬은 총 5번의 패스(n-1번)를 진행합니다. 첫 번째 원소(인덱스 0의 5)는 그 자체로 "정렬된 부분 1개짜리 배열"로 취급하고, 인덱스 1부터 하나씩 꺼내 삽입합니다.

패스	삽입할 값(key)	비교 대상과 결과	비교/이동 횟수	패스 종료 후 배열
시작	-	-	-	[5, 2, 4, 6, 1, 3]
1회전 (i=1)	2	5 > 2 → 5를 오른쪽으로 이동, 왼쪽 끝에 도달 → 2 삽입	비교 1회 · 이동 1회	[2, 5, 4, 6, 1, 3]
2회전 (i=2)	4	5 > 4 → 이동, 2 < 4 → 비교 중단, 5가 있던 자리에 4 삽입	비교 2회 · 이동 1회	[2, 4, 5, 6, 1, 3]
3회전 (i=3)	6	5 < 6 → 즉시 비교 중단(이동 없음), 제자리 유지	비교 1회 · 이동 0회	[2, 4, 5, 6, 1, 3] (변화 없음)
4회전 (i=4)	1	6>1, 5>1, 4>1, 2>1 → 모두 이동, 맨 앞에 1 삽입	비교 4회 · 이동 4회	[1, 2, 4, 5, 6, 3]
5회전 (i=5)	3	6>3, 5>3, 4>3 → 이동, 2<3 → 비교 중단, 4가 있던 자리에 3 삽입	비교 4회 · 이동 3회	[1, 2, 3, 4, 5, 6]

다섯 번의 패스를 모두 거치면 배열은 [1, 2, 3, 4, 5, 6]으로 완전히 정렬됩니다. 이 예제에서 발생한 전체 비교 횟수는 1+2+1+4+4 = 12회, 전체 이동(shift) 횟수는 1+1+0+4+3 = 9회입니다. 특히 3회전에서는 6이 이미 제자리(가장 큰 값)에 있었기 때문에 비교만 한 번 하고 아무것도 이동하지 않았다는 점을 눈여겨봐야 합니다. 시험에서 "매 회전마다 반드시 이동이 일어난다"고 착각하면 이런 문제에서 틀리기 쉽습니다.

💡 시간복잡도: 왜 최선은 O(n)이고 최악은 O(n²)인가

삽입 정렬의 시간복잡도는 입력 데이터가 정렬에 얼마나 가까운가에 따라 크게 달라지는 것이 특징입니다.

경우	시간복잡도	왜 그런가
최선(Best)	O(n)	배열이 이미 정렬되어 있으면, 각 패스에서 key를 바로 왼쪽 원소와 딱 한 번만 비교하고 "이동할 필요 없음"으로 즉시 멈춥니다. n-1번의 패스마다 비교가 1회씩만 일어나므로 총 비교 횟수는 n-1번 → O(n).
평균(Average)	O(n²)	무작위로 섞인 배열에서는 새로 삽입되는 원소가 평균적으로 이미 정렬된 구간의 절반쯤 되는 위치까지 파고듭니다. 이런 비교·이동이 n개 원소에 걸쳐 누적되면 대략 n²/4 수준이 되어 O(n²)로 수렴합니다.
최악(Worst)	O(n²)	배열이 완전히 역순으로 정렬되어 있으면(예: [6,5,4,3,2,1]) 매 패스마다 정렬된 구간의 모든 원소를 다 비교하고 다 이동해야 합니다. 총 비교·이동 횟수가 1+2+3+...+(n-1) = n(n-1)/2 가 되어 O(n²).

즉 삽입 정렬은 "데이터가 거의 정렬되어 있을 때 특히 강한" 알고리즘입니다. 위 예제에서 3회전(key=6)이 비교 1회로 끝난 것도 그 부분이 이미 제자리였기 때문이며, 이는 최선의 경우가 왜 빠른지를 그대로 보여주는 축소판입니다.

💡 안정 정렬(Stable Sort)인 이유

삽입 정렬은 안정 정렬입니다. 비교 조건이 arr[j] > key(엄격한 부등호)이기 때문에, key와 같은 값을 만나면 그 값을 지나쳐서 이동시키지 않고 바로 멈춰서 key를 그 뒤에 삽입합니다. 그 결과 값이 같은 두 원소는 정렬 후에도 원래 배열에서의 상대적인 순서가 그대로 유지됩니다. 또한 별도의 배열을 새로 만들지 않고 주어진 배열 안에서 위치만 바꾸므로 제자리 정렬(in-place sort)이며, 추가로 필요한 공간은 key를 담는 임시 변수 하나뿐이라 공간복잡도는 O(1)입니다.

버블 정렬·선택 정렬과의 차이

정렬 알고리즘	평균/최악	최선	안정 정렬	동작 방식
삽입 정렬	O(n²)	O(n)	안정	정렬된 구간에 새 원소를 알맞은 위치로 끼워 넣음
버블 정렬	O(n²)	O(n) (조기 종료 플래그 사용 시)	안정	인접한 두 원소를 비교해 크면 계속 교환(swap)하며 앞으로 밀어냄
선택 정렬	O(n²)	O(n²) (조기 종료 불가)	불안정	매 회전마다 남은 구간에서 최솟값을 찾아 맨 앞과 교체(swap)

세 알고리즘 모두 평균·최악은 O(n²)로 동일하지만, 선택 정렬은 최선의 경우에도 항상 모든 비교를 수행하기 때문에 O(n²)에서 벗어나지 못합니다. 반면 삽입 정렬과 버블 정렬(조기 종료 조건을 넣은 경우)은 이미 정렬된 데이터를 만나면 O(n)까지 빨라질 수 있습니다. 또한 선택 정렬은 교환(swap) 자체는 최대 n-1번으로 적지만 불안정 정렬이라는 점이, 삽입 정렬은 이동(shift) 횟수는 많아질 수 있지만 안정 정렬이라는 점이 시험에서 자주 대비되어 출제됩니다.

💡 최악의 경우를 숫자로 직접 검산하기

같은 배열을 완전히 거꾸로 뒤집은 [6, 5, 4, 3, 2, 1]로 최악의 경우를 검산해보겠습니다. 1회전(key=5)은 6과 1회 비교 후 이동 1회, 2회전(key=4)은 6·5와 2회 비교 후 이동 2회, 3회전(key=3)은 3회 비교·3회 이동, 4회전(key=2)은 4회 비교·4회 이동, 5회전(key=1)은 5회 비교·5회 이동입니다. 합산하면 비교와 이동 각각 1+2+3+4+5 = 15회, 즉 n=6일 때 n(n-1)/2 = 6×5/2 = 15와 정확히 일치합니다. 이 공식은 최악의 경우 총 비교(또는 이동) 횟수를 묻는 문제에서 그대로 활용할 수 있습니다.

반대로 앞서 다룬 [5, 2, 4, 6, 1, 3]에서는 총 비교가 12회로, 최악의 경우인 15회보다 적었습니다. 이는 3회전에서 6이 이미 제자리였기 때문에 발생한 차이이며, "같은 크기의 배열이라도 초기 배열 상태에 따라 실제 비교·이동 횟수는 달라진다"는 사실을 숫자로 보여줍니다. 즉 시간복잡도 O(n²)은 상한을 나타내는 것이지, 모든 입력에서 똑같은 횟수가 나온다는 뜻이 아닙니다.

💡 실무에서는 어떻게 쓰이나

삽입 정렬은 원소 수가 많은 배열 전체를 정렬할 때는 O(n²)이라는 한계 때문에 잘 쓰이지 않지만, 원소 수가 적은 부분 배열을 정렬할 때는 오히려 퀵 정렬이나 병합 정렬보다 빠릅니다. 비교·이동 연산 자체의 오버헤드가 작고, 재귀 호출이 없기 때문입니다. 그래서 실제 언어 표준 라이브러리의 정렬 함수(자바의 Arrays.sort, 파이썬의 팀소트(Timsort) 등)는 배열을 잘게 나눈 뒤 크기가 작은 구간(보통 수십 개 이하)에는 삽입 정렬을 끼워 넣는 하이브리드 전략을 씁니다. "삽입 정렬은 무조건 느리다"고 단정하기보다, 데이터 규모와 정렬 상태에 따라 강점이 달라지는 알고리즘으로 이해하는 것이 정확합니다.

💡 코드로 확인하기

파이썬과 자바로 각각 구현한 삽입 정렬입니다. 안쪽 while 반복문의 조건 arr[j] > key가 안정 정렬을 만드는 핵심이라는 점을 코드에서도 확인할 수 있습니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 정렬된 구간(0~i-1)을 뒤에서부터 훑으며 key보다 큰 값을 한 칸씩 밀어낸다
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        // 정렬된 구간(0~i-1)을 뒤에서부터 훑으며 key보다 큰 값을 한 칸씩 밀어낸다
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

💡 시험에서 자주 틀리는 함정

• 패스 횟수 착각 — 원소가 n개면 패스는 n번이 아니라 n-1번입니다. 첫 번째 원소는 삽입 대상이 아니라 "정렬된 구간의 시작점"으로 취급되기 때문입니다.
• 모든 회전에서 이동이 일어난다는 착각 — 위 예제의 3회전(key=6)처럼, 삽입할 값이 이미 제자리에 있으면 비교만 하고 이동은 0회일 수 있습니다. "회전 수 = 이동 횟수"로 단순 계산하면 틀립니다.
• 비교 횟수와 이동 횟수를 같은 값으로 착각 — 최악의 경우(완전 역순)에는 비교 횟수와 이동 횟수가 둘 다 n(n-1)/2로 같아지지만, 일반적인 배열에서는 비교 횟수가 이동 횟수보다 항상 1회씩 더 많습니다(멈추기 위한 비교 1회가 추가로 필요하거나, 왼쪽 끝에 닿아 멈추는 경우 제외). 문제에서 특정 예제를 줄 때는 반드시 직접 손으로 세어야 합니다.
• 최선의 경우를 O(n²)으로 착각 — "이미 정렬된 배열"이라는 조건이 문제에 주어지면 삽입 정렬은 O(n)입니다. O(n²)은 무작위 또는 역순 데이터에서만 성립합니다.
• 안정 정렬 여부 혼동 — 삽입 정렬과 버블 정렬은 안정 정렬, 선택 정렬은 불안정 정렬입니다. 세 알고리즘을 묶어 "정렬 알고리즘의 안정성" 표로 묻는 문제가 자주 출제되므로 셋을 짝지어 외워두는 것이 안전합니다.

💡 자주 묻는 질문

삽입 정렬은 몇 번의 패스(회전)를 진행하나요?

원소 개수가 n개라면 총 n-1번의 패스를 진행합니다. 인덱스 1번 원소부터 마지막 원소까지 순서대로 하나씩 꺼내 이미 정렬된 앞부분에 삽입하기 때문입니다.

최선의 경우 비교 횟수는 정확히 몇 번인가요?

배열이 이미 오름차순으로 정렬되어 있다면, 각 패스마다 key를 바로 왼쪽 원소와 딱 한 번 비교한 뒤 곧바로 멈춥니다. 따라서 총 비교 횟수는 패스 수와 같은 n-1번이며, 이동(shift)은 한 번도 일어나지 않습니다.

삽입 정렬과 선택 정렬 중 어느 쪽이 더 빠른가요?

이론적인 평균·최악 시간복잡도는 둘 다 O(n²)로 동일합니다. 다만 데이터가 이미 어느 정도 정렬되어 있는 상황이라면 삽입 정렬이 O(n)에 가깝게 빨라질 수 있는 반면, 선택 정렬은 데이터 상태와 무관하게 항상 같은 횟수만큼 비교합니다. 그래서 "거의 정렬된 데이터"에는 삽입 정렬이, 이동(쓰기) 비용이 비교보다 훨씬 비싼 환경에서는 교환 횟수가 적은 선택 정렬이 유리하다고 설명하는 경우가 많습니다.

💡 지금 시작하기

삽입 정렬은 원리 자체는 단순하지만, 회전별로 배열이 정확히 어떻게 바뀌는지 손으로 추적하는 연습이 되어 있지 않으면 시험장에서 계산 실수를 하기 쉽습니다. 이번 글에서 정리한 표를 손으로 한 번 더 따라 그려보면서 비교·이동 횟수를 스스로 세어보는 것을 추천합니다. 자료구조 정렬 알고리즘 전체를 무료 강의로 이어서 학습할 수 있습니다.

강의 자세히 보기 →