버블·선택·삽입 정렬, 동작 원리와 실무 선택 기준
버블·선택·삽입 정렬은 모두 평균 O(n²) 알고리즘이지만 동작 방식과 안정성, 교환 횟수가 다르다. 세 알고리즘의 원리와 파이썬 코드, 그리고 파이썬·자바·C++ 표준 라이브러리가 작은 배열에 여전히 삽입 정렬을 쓰는 이유를 정리했다.
목차
버블 정렬, 선택 정렬, 삽입 정렬은 프로그래밍을 배울 때 가장 먼저 만나는 세 가지 기본 정렬 알고리즘이다. 셋 다 평균과 최악의 경우 O(n²)의 시간이 걸려 대규모 데이터에는 부적합하지만, 동작 방식과 안정성, 교환 횟수가 서로 달라 쓰임새가 갈린다. 결론부터 말하면 거의 정렬된 데이터에는 삽입 정렬, 원소를 옮기는 비용이 큰 데이터에는 선택 정렬이 유리하고, 버블 정렬은 실무보다 학습용으로 의미가 크다.
이 글은 세 알고리즘의 동작 원리와 파이썬 코드, 시간 복잡도, 그리고 실제 표준 라이브러리가 작은 배열에서 이들 중 하나를 여전히 쓰는 이유까지 다룬다. 언어별 세부 최적화나 특정 하드웨어 튜닝까지 파고들지 않고, 세 알고리즘의 공통 원리에 초점을 맞춘다. 근거로는 파이썬 공식 정렬 문서와 Tim Peters가 작성한 CPython listsort.txt를 참조했다.
세 알고리즘을 한눈에 구분하기
세 알고리즘은 정렬되지 않은 부분에서 값을 어떻게 골라 정렬된 자리로 옮기느냐가 다르다. 버블 정렬은 인접한 두 값을 비교해 어긋나면 바로 맞바꾸고, 이 과정을 반복해 큰 값을 배열 끝으로 밀어낸다. 선택 정렬은 정렬 안 된 구간에서 가장 작은 값을 찾아 맨 앞으로 가져온다. 삽입 정렬은 이미 정렬된 앞부분에 새 값을 하나씩 알맞은 자리에 끼워 넣는다.
세 알고리즘의 평균과 최악 시간 복잡도는 모두 O(n²)다. 원소가 n개일 때 비교 횟수가 대략 n의 제곱에 비례한다는 뜻으로, 원소가 10배 늘면 실행 시간은 약 100배가 된다. 그래서 수만 건 이상을 정렬할 때는 O(n log n) 알고리즘인 퀵 정렬·병합 정렬·힙 정렬을 쓴다. 다만 세부 성질은 아래 표처럼 갈린다.
| 알고리즘 | 평균·최악 시간 | 최선 시간 | 안정성 |
|---|---|---|---|
| 버블 정렬 | O(n²) | O(n) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | 불안정 |
| 삽입 정렬 | O(n²) | O(n) | 안정 |
여기서 안정성(같은 값의 원래 순서가 정렬 후에도 유지되는 성질)은 실무에서 생각보다 자주 문제가 된다. 예를 들어 주문 목록을 금액순으로 정렬할 때 금액이 같은 주문들이 원래 입력 순서를 지키면 안정 정렬이다. 버블 정렬과 삽입 정렬은 안정적이고, 선택 정렬은 일반적인 구현에서 불안정하다.
버블 정렬: 인접한 값을 맞바꿔 큰 값을 끝으로
버블 정렬은 배열을 왼쪽부터 훑으며 인접한 두 값을 비교하고, 앞이 뒤보다 크면 자리를 바꾼다. 한 번 끝까지 훑으면 가장 큰 값이 맨 오른쪽에 확정된다. 큰 값이 거품처럼 위로 떠오른다고 해서 버블 정렬이라 부른다. 원소가 n개라면 이 훑기를 최대 n-1번 반복한다.
기본형은 데이터가 이미 정렬돼 있어도 끝까지 다 훑어 항상 O(n²)이다. 하지만 한 번 훑는 동안 교환이 한 번도 없었다면 이미 정렬이 끝났다는 뜻이다. 교환 발생 여부를 기록하는 플래그를 두면 그 시점에 반복을 멈출 수 있고, 이 최적화를 넣으면 이미 정렬된 입력에서는 한 번만 훑고 끝나 최선의 경우 O(n)이 된다.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr역순 입력 같은 최악의 경우에는 교환이 약 n²/2번 일어난다. 비교뿐 아니라 실제 값 이동이 그만큼 많다는 뜻이라, 원소 하나를 옮기는 비용이 큰 데이터에서는 버블 정렬이 특히 불리하다. 조기 종료 플래그가 있어도 최악의 경우는 여전히 O(n²)이라는 점도 기억해 둘 만하다.
선택 정렬: 최솟값을 찾아 앞으로 보내기
선택 정렬은 정렬 안 된 구간 전체를 훑어 가장 작은 값을 찾고, 그 값을 구간의 맨 앞과 한 번 맞바꾼다. 그러면 맨 앞 한 자리가 확정된다. 다음에는 두 번째 자리부터 같은 일을 반복한다. 최솟값을 골라 앞으로 보내는 방식이라 선택 정렬이다.
선택 정렬의 특징은 교환 횟수가 고정된다는 점이다. 매 단계에서 최솟값을 찾을 때 비교는 많이 하지만 실제 자리 교환은 단계마다 한 번뿐이다. 그래서 원소 n개를 정렬할 때 비교는 입력 상태와 무관하게 항상 n(n-1)/2번으로 O(n²)이고, 교환은 정확히 n-1번이다. 값을 디스크에 쓰거나 큰 객체를 통째로 복사하는 등 교환 자체가 비싼 상황에서는 이 쓰기 최소화 성질이 장점이 된다.
단점은 두 가지다. 첫째, 데이터가 이미 정렬돼 있어도 비교를 건너뛰지 못해 최선의 경우도 O(n²)다. 둘째, 멀리 떨어진 값을 통째로 맞바꾸는 과정에서 같은 값의 상대 순서가 뒤집힐 수 있어 일반적인 구현은 불안정하다. 순서가 중요한 데이터를 다룬다면 이 점을 반드시 확인해야 한다.
삽입 정렬: 정렬된 앞부분에 끼워 넣기
삽입 정렬은 배열의 두 번째 원소부터 시작해, 그 값을 왼쪽의 이미 정렬된 부분에서 알맞은 자리에 끼워 넣는다. 끼워 넣을 자리를 찾는 동안 그보다 큰 값들은 오른쪽으로 한 칸씩 민다. 카드 게임에서 손에 든 패를 하나씩 제자리에 꽂아 정렬하는 방식과 같다.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr삽입 정렬의 강점은 입력이 거의 정렬된 상태일 때 드러난다. 각 원소가 제자리에서 몇 칸만 움직이면 되므로, 완전히 정렬된 입력에서는 안쪽 while 반복이 매번 곧바로 끝나 최선의 경우 O(n)이다. 값이 같을 때는 자리를 바꾸지 않고 그대로 두므로 안정적이기도 하다. 거의 정렬된 데이터에 강하고 안정적이라는 이 두 성질 때문에 삽입 정렬은 세 알고리즘 중 실무에서 가장 자주 재등장한다.
O(n²)인데 표준 라이브러리는 왜 아직 삽입 정렬을 쓸까
작은 배열에서는 삽입 정렬이 오히려 빠르기 때문이다. O(n log n) 알고리즘은 재귀 호출과 분할 같은 부가 비용이 있는데, 원소가 수십 개 이하로 적으면 이 부가 비용이 O(n²) 대비 이득보다 커진다. 그래서 널리 쓰이는 표준 라이브러리들은 큰 배열은 빠른 알고리즘으로 처리하다가 구간이 충분히 작아지면 삽입 정렬로 갈아탄다.
Tim Peters가 작성한 CPython의 listsort.txt에 따르면 파이썬의 리스트 정렬(Timsort)은 원소가 64개 미만이면 사실상 이진 삽입 정렬로 축소된다. OpenJDK의 DualPivotQuicksort 소스 코드는 원소가 47개 미만인 구간에 삽입 정렬을 적용한다. C++ 표준 라이브러리 문서 사이트인 cppreference가 설명하는 std::sort의 인트로 정렬 구현(libstdc++)은 부분 구간이 16개 미만으로 작아지면 삽입 정렬로 마무리한다.
| 구현 | 삽입 정렬로 처리하는 크기 | 큰 배열의 주 알고리즘 |
|---|---|---|
| CPython (Timsort) | 원소 64개 미만 | 병합 정렬 기반 Timsort |
| OpenJDK Arrays.sort | 원소 47개 미만 | 듀얼 피벗 퀵 정렬 |
| libstdc++ std::sort | 부분 구간 16개 미만 | 인트로 정렬(퀵+힙) |
세 임계값이 서로 다른 것은 언어와 자료형, 벤치마크 환경이 다르기 때문이며 모두 실험으로 정한 경험적 값이다. 파이썬 공식 정렬 문서에서 확인할 수 있듯 파이썬의 기본 정렬은 안정 정렬인데, 그 바탕에 안정 정렬인 삽입 정렬이 깔려 있는 것도 우연이 아니다. 빅오 표기만으로 실제 성능을 판단할 수 없고 상수 항과 부가 비용까지 따져야 한다는 이 관점은, 리플렉션처럼 런타임에 타입을 다루는 기능의 성능 대가를 따질 때도 똑같이 필요하다. 정리하면 삽입 정렬은 단독 알고리즘으로는 느리지만, 빠른 알고리즘의 마지막 단계를 채우는 부품으로 지금도 현역이다.
어떤 상황에 무엇을 고를까
세 알고리즘 중 실무에서 직접 손으로 쓸 일이 있다면 대부분 삽입 정렬이다. 판단 기준을 정리하면 다음과 같다.
- 거의 정렬된 데이터를 다듬을 때는 삽입 정렬이 낫다. 로그처럼 대체로 시간순인데 일부만 어긋난 데이터, 또는 이미 정렬된 목록에 소수의 새 항목이 추가된 경우 O(n)에 가깝게 끝난다.
- 원소 하나를 옮기는 비용이 클 때는 선택 정렬이 유리하다. 교환이 n-1번으로 고정되므로 큰 레코드를 통째로 이동하거나 쓰기 연산이 비싼 매체를 다룰 때 이동 횟수를 줄인다.
- 원소가 수십 개 이하로 아주 적을 때는 삽입 정렬을 쓴다. 표준 라이브러리도 이 구간에서 삽입 정렬로 갈아타며, 코드가 짧아 직접 구현하기도 쉽다.
- 정렬 개념을 가르치거나 배울 때는 버블 정렬이 무난하다. 인접 교환이라는 동작이 눈에 잘 보여 시각화와 이해에 좋다. 다만 성능 이점은 없어 실제 데이터 처리에는 권하지 않는다.
수천 건 이상을 정렬한다면 세 알고리즘 대신 언어가 제공하는 표준 정렬 함수를 쓰는 편이 낫다. 파이썬의 sorted()와 list.sort(), 자바의 Arrays.sort(), C++의 std::sort()는 모두 앞에서 본 하이브리드 방식으로 대량 데이터에 최적화돼 있다. 기본 정렬 세 가지를 배우는 목적은 이 표준 함수를 대체하기 위해서가 아니라, 그 안에서 무슨 일이 일어나는지 이해하기 위해서다.
직접 구현할 때 걸리기 쉬운 함정
세 알고리즘은 코드가 짧지만, 미묘한 실수가 성능이나 정확성을 망치는 지점이 정해져 있다.
- 버블 정렬의 조기 종료 플래그 누락 — swapped 플래그 없이 이중 반복만 돌리면 이미 정렬된 입력에서도 항상 O(n²)이다. 최선의 경우 O(n)이라는 이점은 이 플래그가 있을 때만 성립한다.
- 반복 경계의 off-by-one — 인접 비교에서 arr[j]와 arr[j+1]을 볼 때 안쪽 반복을 배열 끝까지 두면 인덱스가 배열 밖으로 나간다. 버블 정렬의 안쪽 반복은 n-1-i까지, 삽입 정렬의 while은 j가 0 이상일 때까지로 경계를 정확히 잡아야 한다.
- 선택 정렬의 안정성 오해 — 선택 정렬을 안정 정렬로 착각하고 순서가 중요한 데이터에 쓰면 같은 값의 상대 순서가 뒤집힌다. 안정성이 필요하면 삽입 정렬이나 언어 표준의 안정 정렬을 쓴다.
- 선택 정렬에서 매번 교환 — 더 작은 값을 만날 때마다 곧바로 교환하면 교환 횟수가 n-1번을 넘어 쓰기 최소화라는 장점이 사라진다. 한 단계에서는 최솟값의 위치만 기억해 두었다가 단계 끝에서 한 번만 교환한다.
