정렬

삽입 정렬

카드를 한 장씩 끼워 넣기

카드 여섯 장을 작은 수부터 왼쪽에 늘어놓아 보세요. 한 장씩 받아서 왼쪽에 모인 카드 사이에 끼워 넣을 자리를 찾습니다.

제자리에 가까울수록 적게 견준다

카드 모양을 바꿔 가며 눌러 보세요. 견주는 횟수가 달라집니다.

• 손패는 늘 정렬돼 있다 — 아까도 손패는 한 번도 흐트러지지 않았다. 새 카드는 정렬된 줄에 끼우기만 하면 된다
• 이미 정렬된 카드 — 카드마다 한 번만 견주고 끝난다. 카드가 n장이면 n−1번이다
• 거꾸로 선 카드 — 모든 카드를 맨 앞까지 민다. n(n−1)/2번으로 선택 정렬과 같아진다

거꾸로 선 1만 장은 약 5천만 번 견주고, 직접 재 보니 Python 3.14 에서 1.5초 걸렸습니다. 이미 정렬된 1만 장은 0.0004초였습니다. 컴퓨터마다 다릅니다.

코드는 빈자리를 왼쪽으로 옮기는 것이 전부다

다음을 눌러 한 줄씩 넘기며 빈자리가 왼쪽으로 옮겨 오는 걸 보세요. j -= 1 줄은 켜지지 않습니다. 바로 다음 줄에 새 j 가 이미 보입니다.

• key — 손에 든 카드. 줄 위쪽에 서 있다
• j — 지금 견주는 칸. 빈자리 바로 왼쪽이다
• j >= 0 and arr[j] > key — 맨 앞이 아니고 그 카드가 더 크면 민다. 아니면 멈춘다

삽입 정렬에서 틀리는 자리

• j >= 0 을 빼면 — 가장 작은 카드가 맨 앞까지 오면 j 가 −1 이 되어 arr[-1](맨 끝 카드)과 견준다. 곧 IndexError: list index out of range 가 난다. 맨 앞까지 가는 카드가 없는 1 2 3 은 그대로 맞게 나온다
• > 대신 >= — 같은 값도 넘어간다. 이미 정렬된 1a 1b 2c 가 1b 1a 2c 로 뒤집힌다. > 로 쓰면 2a 2b 1c 가 1c 2a 2b 로 원래 순서가 지켜진다(안정 정렬). 선택 정렬은 같은 값의 순서를 지키지 못한다
• 마지막 arr[j + 1] = key 를 빼면 — 손에 든 카드가 어디에도 놓이지 않는다. 5 2 9 가 5 5 9 가 되어 2 가 사라진다

이럴 때 꺼낸다

실전에서 정렬이 필요할 때는 sorted() 한 줄이면 됩니다. 파이썬의 정렬(Timsort)도 짧은 구간은 삽입 정렬 계열로 정리합니다.

다음 장에서는 반으로 쪼갰다가 정렬된 두 묶음을 합치는 병합 정렬을 봅니다.