삽입 정렬

삽입 정렬은 값을 하나씩 꺼내 이미 줄 세운 앞부분에 끼워 넣습니다. 끼워 넣기를 끝까지 되풀이하면 배열 전체가 순서대로 놓입니다. 작은 배열이나 거의 정렬된 배열은 금방 끝냅니다. 크고 뒤섞인 배열에서는 걸리는 시간이 크게 늘어납니다.

상세

이 절은 삽입 정렬이 받는 것과 내주는 것부터 봅니다. 그다음 값 네 개짜리 배열을 손으로 정렬해 봅니다. 같은 일을 하는 코드도 읽습니다. 끝으로 걸리는 시간과 이 방법을 쓰는 곳을 봅니다.

받는 것과 내주는 것

값을 순서대로 늘어놓는 일을 정렬이라고 합니다. 삽입 정렬은 그 일을 하는 절차 가운데 하나입니다. 넣는 것은 값을 번호 순서대로 나란히 담은 배열입니다. 나오는 것은 같은 값들이 작은 것부터 놓인 배열입니다.

두 값 가운데 어느 쪽이 앞인지는 비교로 가립니다. 숫자라면 작은 쪽이 앞입니다. 주문처럼 필드가 여럿인 값이라면 금액이나 주문 시각 같은 기준 하나를 골라 비교합니다. 삽입 정렬은 이 비교를 되풀이해 순서를 정합니다.

카드 패 정리

카드 게임에서 패를 한 장씩 받는 장면을 떠올려 봅니다. 손에 든 카드는 이미 순서대로 들고 있습니다. 새 카드를 받으면 손패를 훑어 알맞은 틈을 찾아 끼웁니다. 마지막 카드를 받고 나면 손패 전체가 순서대로 놓입니다.

정렬된 앞부분과 남은 뒷부분

삽입 정렬은 배열을 두 부분으로 나눠 봅니다. 왼쪽은 이미 순서대로 놓인 정렬된 앞부분입니다. 오른쪽은 아직 손대지 않은 남은 뒷부분입니다.

처음에는 맨 앞 값 하나만 정렬된 앞부분입니다. 값이 하나뿐이면 이미 정렬돼 있기 때문입니다. 한 차례가 끝날 때마다 뒷부분의 맨 앞 값 하나가 앞부분으로 넘어옵니다. 뒷부분이 비면 정렬이 끝납니다.

정렬된 앞부분은 어느 차례에서나 순서대로 놓여 있습니다. 그래서 새 값은 앞부분 안에서 들어갈 위치만 찾으면 됩니다. 앞부분 전체를 다시 정렬할 필요가 없습니다.

값 하나를 끼워 넣는 과정

한 차례는 뒷부분의 맨 앞 값을 꺼내는 데서 시작합니다. 이 값을 아래에서 꺼낸 값이라고 부릅니다. 꺼낸 값이 있던 칸은 잠시 비어 있게 됩니다.

꺼낸 값 바로 왼쪽 값부터 비교합니다. 왼쪽 값이 꺼낸 값보다 크면 그 값을 한 칸 오른쪽으로 옮깁니다. 오른쪽 칸이 비어 있으니 옮길 수 있습니다. 옮기고 나면 빈 칸이 한 칸 왼쪽으로 옵니다.

왼쪽 값이 꺼낸 값보다 크지 않으면 멈춥니다. 배열 맨 앞에 닿아도 멈춥니다. 멈춘 뒤 비어 있는 칸에 꺼낸 값을 넣습니다.

아래 그림은 이 과정을 한 장으로 보입니다. 가운데 물음의 답이 「예」인 동안 옮기기를 되풀이합니다.

flowchart TD
    A["뒷부분의 맨 앞 값을 꺼낸다"] --> B{"왼쪽 값이 꺼낸 값보다 큰가"}
    B -->|예| C["왼쪽 값을 한 칸 오른쪽으로 옮긴다"]
    C --> B
    B -->|"아니오 · 맨 앞에 닿음"| D["비어 있는 칸에 꺼낸 값을 넣는다"]
    D --> E{"뒷부분에 값이 남았나"}
    E -->|예| A
    E -->|아니오| F["정렬 끝"]

값 네 개를 정렬해 보기

배열 4, 2, 5, 1 을 정렬해 봅니다. 시작할 때 정렬된 앞부분은 맨 앞의 4 하나입니다. 아래 표의 한 줄이 한 차례입니다.

첫 차례에서 꺼낸 2 는 4 보다 작습니다. 그래서 4 를 한 칸 오른쪽으로 옮겼습니다. 비어 있는 맨 앞 칸에는 2 를 넣었습니다.

둘째 차례의 5 는 왼쪽 값 4 보다 큽니다. 비교 한 번에 멈추고 아무것도 옮기지 않았습니다. 이미 순서가 맞는 값은 이렇게 싸게 지나갑니다.

셋째 차례의 1 은 앞부분의 어느 값보다 작습니다. 5, 4, 2 를 차례로 옮기고 맨 앞에 들어갔습니다. 작은 값이 뒤쪽에 있을수록 옮길 값이 많아집니다.

셋째 차례 안에서 배열이 어떻게 바뀌는지 칸 단위로 보면 아래와 같습니다. 이 차례에는 남은 뒷부분이 없습니다. 네 칸 가운데 빈 칸 말고는 모두 정렬된 앞부분입니다. 한 번 옮길 때마다 빈 칸이 한 칸씩 왼쪽으로 옵니다.

flowchart TD
    subgraph T3["셋째 차례 · 꺼낸 값 1"]
        S0["2 · 4 · 5 · 빈 칸"]
        S1["2 · 4 · 빈 칸 · 5"]
        S2["2 · 빈 칸 · 4 · 5"]
        S3["빈 칸 · 2 · 4 · 5"]
        S4["1 · 2 · 4 · 5"]
        S0 -->|"5 가 1 보다 커서 옮긴다"| S1
        S1 -->|"4 를 옮긴다"| S2
        S2 -->|"2 를 옮긴다"| S3
        S3 -->|"맨 앞에 닿아 빈 칸에 1 을 넣는다"| S4
    end

코드로 옮긴 삽입 정렬

같은 절차를 파이썬으로 옮기면 아래와 같습니다. 바깥 for 한 바퀴가 표의 한 차례입니다. 안쪽 while 이 왼쪽 값을 옮기는 부분입니다.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

a = [4, 2, 5, 1]
insertion_sort(a)  # [1, 2, 4, 5]

key 가 꺼낸 값입니다. j 는 지금 비교하는 왼쪽 값의 번호입니다. while 조건이 참인 동안 a[j] 를 한 칸 오른쪽인 a[j + 1] 로 옮깁니다. 반복이 끝나면 비어 있는 a[j + 1] 에 key 를 넣습니다.

while 조건의 j >= 0 은 배열 맨 앞에 닿으면 멈추라는 뜻입니다. 1 처럼 앞부분의 모든 값보다 작은 값은 이 조건에서 멈추고 맨 앞 칸에 들어갑니다.

같은 값끼리의 순서

while 조건의 비교는 a[j] > key 입니다. 왼쪽 값이 꺼낸 값과 같으면 옮기지 않고 멈춥니다. 그래서 같은 값끼리는 원래 앞에 있던 값이 계속 앞에 남습니다.

이 성질을 지키는 정렬을 안정 정렬이라고 합니다. 주문 시각 순으로 쌓인 주문을 금액으로 다시 정렬한다고 해 봅니다. 안정 정렬이면 금액이 같은 주문끼리는 먼저 들어온 주문이 계속 앞에 섭니다.

조건을 a[j] >= key 로 바꾸면 같은 값도 오른쪽으로 옮겨집니다. 그러면 뒤에 있던 값이 앞으로 넘어가 이 성질이 깨집니다. 정렬 결과는 같아 보여도 같은 값끼리의 순서가 달라집니다.

배열 3, 2ᵃ, 2ᵇ 로 두 조건을 견주어 봅니다. 2ᵃ 와 2ᵇ 는 같은 값 2 이고, 원래 2ᵃ 가 앞에 있습니다.

따로 쓰는 메모리

삽입 정렬은 입력 배열 안에서 값을 옮겨 정렬합니다. 따로 쓰는 메모리는 key 와 j 같은 변수 몇 개뿐입니다. 배열이 아무리 커도 이 몇 칸은 늘지 않습니다.

이렇게 입력 배열 말고는 추가 공간이 거의 필요 없는 정렬을 제자리 정렬이라고 합니다. 배열이 커져도 메모리를 더 잡지 않으니 메모리가 빠듯한 곳에서도 쓸 수 있습니다.

모든 정렬이 제자리 정렬은 아닙니다. 병합 정렬은 배열을 반씩 쪼갰다가 합치는 정렬입니다. 합칠 때 배열 크기만큼 공간을 더 씁니다. 메모리가 빠듯할 때 이 차이가 선택을 가릅니다.

걸리는 시간

걸리는 시간은 비교와 옮기기를 몇 번 하느냐로 정해집니다. 그 횟수는 입력이 얼마나 뒤섞였는지에 따라 크게 갈립니다. 이 소절은 이미 정렬된 배열, 거꾸로 정렬된 배열, 무작위로 섞인 배열을 견줍니다.

값의 개수를 n 이라고 적습니다. 빅오 표기법은 n 이 늘 때 시간이 어떤 모양으로 느는지를 적는 약속입니다. O(n) 은 n 이 두 배가 되면 시간도 두 배쯤 된다는 뜻입니다. O(n²) 은 n 이 두 배가 되면 시간이 네 배쯤 된다는 뜻입니다.

삽입 정렬을 다른 정렬과 견줄 때는 O(n log n) 도 나옵니다. log n 은 n 을 절반씩 나누어 1 에 닿기까지 나눈 횟수입니다. n 이 1,000 이면 10 번쯤입니다. O(n log n) 은 n 이 두 배가 되면 시간이 두 배를 조금 넘게 는다는 뜻입니다.

이미 정렬된 배열이 가장 일찍 끝납니다. 차례마다 왼쪽 값 하나와 비교하고 바로 멈춥니다. 차례가 n − 1 번이니 모두 O(n) 입니다.

거꾸로 정렬된 배열이 가장 오래 걸립니다. 꺼낸 값이 매번 앞부분의 모든 값보다 작아서 맨 앞까지 갑니다. k 번째 차례에서 k 개를 옮기니 모두 1 + 2 + … + (n − 1), 곧 n(n − 1)/2 번입니다. 이것이 O(n²) 입니다.

값이 1,000 개일 때로 견주어 봅니다. 이미 정렬된 배열은 비교 999 번으로 끝납니다. 거꾸로 된 배열은 옮기기만 50만 번쯤 합니다.

무작위로 섞인 배열은 그 사이입니다. 꺼낸 값은 평균으로 앞부분의 절반쯤을 지나갑니다. 거꾸로 된 배열의 절반쯤 일합니다. 절반이어도 O(n²) 입니다.

세 경우를 모으면 아래 표와 같습니다.

가장 일찍 끝나는 입력을 최선의 경우, 가장 오래 걸리는 입력을 최악의 경우라고 부릅니다. 삽입 정렬은 두 경우가 O(n) 과 O(n²) 으로 크게 벌어집니다. 입력이 어떤 모양인지 알면 걸리는 시간을 꽤 가늠할 수 있습니다.

뒤바뀐 쌍과 옮기는 횟수

옮기는 횟수는 입력만 보고도 셀 수 있습니다. 배열에서 앞에 있는 값이 뒤에 있는 값보다 크면 그 둘은 순서가 뒤바뀐 쌍입니다.

한 번 옮길 때마다 이런 쌍이 딱 하나 풀립니다. 옮기는 값은 꺼낸 값보다 크면서 꺼낸 값보다 앞에 있던 값입니다. 그 둘이 바로 뒤바뀐 쌍입니다. 옮기고 나면 꺼낸 값이 그 값보다 앞에 섭니다.

옮기는 횟수는 곧 뒤바뀐 쌍의 수입니다. 앞의 4, 2, 5, 1 에는 뒤바뀐 쌍이 넷 있습니다. (4, 2) · (4, 1) · (2, 1) · (5, 1) 입니다. 표에서 옮긴 값도 4 하나와 5, 4, 2 셋을 합쳐 넷이었습니다.

걸리는 시간은 n 에 뒤바뀐 쌍의 수를 더한 만큼입니다. 차례마다 비교를 적어도 한 번 하니 n 만큼은 늘 듭니다. 여기에 옮기기가 뒤바뀐 쌍의 수만큼 더해집니다.

거의 정렬된 배열에는 뒤바뀐 쌍이 몇 개 없습니다. 더해지는 쪽이 작으니 삽입 정렬은 그런 배열을 O(n) 에 가깝게 정렬합니다.

입력이 이미 정렬된 정도에 따라 시간이 줄어드는 정렬을 적응형 정렬(adaptive sort)이라고 합니다. 삽입 정렬이 그 대표입니다. 거의 정렬된 데이터가 자주 들어오는 곳에서 이 성질이 쓸모 있습니다.

삽입 정렬을 쓰는 곳

이 소절은 삽입 정렬이 실무에서 맡는 일 둘을 봅니다. 큰 정렬의 마무리와, 값이 하나씩 도착하는 정렬입니다.

퀵 정렬과 병합 정렬은 배열을 작은 조각으로 쪼개 가며 정렬합니다. 값이 많으면 O(n log n) 인 이쪽이 훨씬 빠릅니다. 하지만 값이 적으면 O(n²) 과 O(n log n) 의 차이가 작습니다. 그때는 준비할 일이 적은 쪽이 먼저 끝납니다.

쪼개 가며 정렬하는 방법에는 준비할 일이 따릅니다. 조각마다 함수가 자기 자신을 다시 부릅니다. 이것이 재귀 호출입니다. 삽입 정렬에는 재귀 호출도, 배열을 쪼개는 준비도, 추가 메모리도 없습니다.

그래서 퀵 정렬과 병합 정렬도 조각이 작아지면 삽입 정렬로 넘깁니다. 쪼갠 조각에 값이 몇 개 안 남으면 거기서부터 삽입 정렬로 마무리하는 구현이 흔합니다.

아래 그림은 쪼개기가 세 층 내려간 모습입니다. 맨 아래의 작은 조각들만 삽입 정렬이 맡습니다.

flowchart TD
    A["큰 배열"] --> B["조각"]
    A --> C["조각"]
    B --> D["작은 조각"]
    B --> E["작은 조각"]
    C --> F["작은 조각 둘"]
    D --> G["값이 몇 개뿐 → 삽입 정렬로 마무리"]
    E --> G
    F --> G

이렇게 두 방법을 섞은 정렬을 하이브리드 정렬이라고 부릅니다. 팀 정렬과 인트로 정렬이 그 예입니다. 여러 언어의 표준 라이브러리 정렬이 하이브리드 정렬을 씁니다. 개발자가 직접 짜지 않아도 삽입 정렬은 라이브러리 안에서 돌고 있습니다.

값이 한 번에 다 오지 않고 하나씩 도착해도 삽입 정렬은 돕니다. 새 값이 오면 정렬된 앞부분에 끼워 넣으면 됩니다. 그러면 그때까지 받은 값은 언제나 정렬돼 있습니다.

입력을 다 받기 전에 처리를 시작해 받은 만큼의 답을 늘 쥐고 있는 알고리즘을 온라인 알고리즘이라고 합니다. 점수가 하나씩 들어오는 순위표가 예입니다. 새 점수가 오면 순위표 안에 끼워 넣습니다. 전체를 처음부터 다시 정렬하지 않습니다.

삽입 정렬을 피하는 곳

값이 많고 뒤섞인 배열에서는 O(n²) 이 그대로 드러납니다. 값이 백만 개면 옮기는 횟수가 수천억 번 단위로 늘어납니다. 같은 배열을 O(n log n) 정렬은 수천만 번 단위의 일로 끝냅니다.

그런 배열에는 O(n log n) 정렬을 씁니다. 병합 정렬과 힙 정렬이 그렇습니다. 퀵 정렬도 대개 그만큼에 끝납니다. 대부분의 언어에서는 표준 라이브러리의 정렬 함수를 부르는 것으로 충분합니다. 그 함수 안에도 삽입 정렬이 들어 있습니다.

삽입 정렬을 고친 변형

들어갈 위치를 찾는 데 이진 탐색을 쓰는 변형이 있습니다. 이진 탐색은 정렬된 배열의 가운데 값을 보고 절반씩 버려 가며 위치를 찾는 방법입니다. 정렬된 앞부분은 늘 정렬돼 있으니 이 방법을 쓸 수 있습니다.

이 변형을 이진 삽입 정렬이라고 합니다. 비교는 앞부분을 절반씩 버리는 횟수, 곧 log n 번쯤으로 줄어듭니다. 앞부분이 1,000 개면 10 번쯤입니다. 하지만 비운 칸까지 값을 한 칸씩 옮기는 일은 줄지 않습니다. 그래서 가장 오래 걸리는 입력에서는 여전히 O(n²) 입니다.

셸 정렬은 몇 칸씩 건너뛴 값들끼리 먼저 삽입 정렬합니다. 4칸 간격이면 1·5·9번째 값끼리, 2·6·10번째 값끼리 모아 정렬합니다. 멀리 떨어져 뒤바뀐 값이 한 번에 여러 칸을 건너 제 위치 가까이 갑니다.

셸 정렬은 간격을 줄여 가다 마지막에 1칸 간격, 곧 보통의 삽입 정렬로 끝냅니다. 그때는 배열이 거의 정렬돼 있어 옮길 값이 적습니다.

관련 항목

삽입 정렬이 속하는 상위 분류

알고리즘 · 정렬 알고리즘 · 정렬 · 비교 정렬

삽입 정렬을 고쳐 만든 변형

이진 삽입 정렬 · 셸 정렬 · 라이브러리 정렬

삽입 정렬 대신 쓸 수 있는 정렬 알고리즘

선택 정렬 · 버블 정렬 · 병합 정렬 · 퀵 정렬 · 힙 정렬 · 계수 정렬 · 기수 정렬

작은 조각을 삽입 정렬에 맡기는 하이브리드 정렬

팀 정렬 · 인트로 정렬 · pdqsort

삽입 정렬이 지키는 성질

안정 정렬 · 제자리 정렬 · 적응형 정렬 · 온라인 알고리즘

삽입 정렬의 비용을 재는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 점근 표기법

삽입 정렬이 값을 담아 도는 자료구조

배열 · 연결 리스트 · 동적 배열

삽입 정렬이 안에서 쓰는 연산

비교 함수 · 정렬 키 · 이진 탐색 · 순차 탐색