버블·선택·삽입 정렬의 특성과 선택 기준
Bubble Sort, Selection Sort, Insertion Sort의 시간복잡도·안정성·교환 비용을 비교하고 입력 특성별 선택 기준을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
작은 입력에서 달라지는 정렬 선택
Bubble Sort, Selection Sort, Insertion Sort는 비교 기반 정렬이며 평균·최악 시간복잡도가 O(n²)이다. 큰 입력을 위한 범용 정렬로 쓰기에는 적합하지 않지만, 작은 배열이나 거의 정렬된 데이터, 하이브리드 정렬의 보조 루틴에서는 메모리 특성과 상수항이 선택 기준이 된다.
세 알고리즘 모두 제자리(in-place) 구현이 쉽고 추가 메모리 사용이 거의 없다. 다만 비교와 교환의 방식, 입력 분포에 대한 반응, 안정 정렬 여부는 서로 다르다.
비교와 이동 방식이 만드는 차이
Bubble Sort는 인접한 원소를 비교하고 교환하면서 큰 값 또는 작은 값을 매 패스마다 배열 끝으로 보낸다. 한 패스에서 교환이 없으면 종료하는 최적화를 적용할 수 있다. 교환 빈도가 높은 편이므로 스왑 비용이 큰 환경에는 불리하다.
Selection Sort는 아직 정렬하지 않은 구간에서 최소값 또는 최대값을 찾아 앞쪽 원소와 교환한다. 비교 횟수는 항상 n(n−1)/2로 고정되고, 교환 횟수는 최대 n−1이다. 입력 분포의 영향을 거의 받지 않으며, 교환 비용이 큰 저장장치나 임베디드 환경에서 선택할 근거가 된다.
Insertion Sort는 현재 원소를 왼쪽의 정렬된 구간 안으로 이동시킨다. 입력이 이미 정렬에 가까울수록 이동량이 줄어 최선의 경우 O(n)에 가까워진다. 온라인(스트리밍) 삽입에도 자연스럽게 맞고, 세 알고리즘 가운데 캐시 지역성이 상대적으로 양호하다.
Bubble Sort와 Insertion Sort는 안정 정렬로 구현할 수 있다. Selection Sort의 기본 구현은 비안정이며, 안정성을 보완하려면 추가 로직과 비용이 필요하다.
삽입 정렬이 배열을 확장하는 흐름
성능과 운영 특성 비교
| 알고리즘 | 성능(비교/교환, 최선/평균/최악) | 확장성 | 일관성 | 안정성 | 운영 편의 |
|---|---|---|---|---|---|
| Bubble | 비교 ~ n²/2, 교환 많음, 최선 O(n)·평균/최악 O(n²) | 낮음(큰 n 비권장) | 입력 분포 민감(조기 종료 시 유리) | 안정 정렬 구현 가능 | 구현 매우 단순, 최적화 여지 적음 |
| Selection | 비교 고정 ~ n²/2, 교환 ≤ n−1 | 낮음(큰 n 비권장) | 입력 분포 무감 | 비안정(추가 로직으로 안정화 가능하나 비용 증가) | 스왑 비용 큰 환경 유리, 예측 가능 |
| Insertion | 비교·이동: 데이터 의존, 최선 O(n)·평균/최악 O(n²) | 낮음(하이브리드의 보조용 적합) | 거의 정렬된 입력에 강함 | 안정 정렬 | 구현 단순, 캐시 친화성 양호 |
하이브리드 정렬과 비용 제약 환경
로그 버퍼, 스케줄링 큐, GUI 정렬처럼 n ≤ 32~64 구간의 소규모 데이터에는 Insertion Sort를 우선 고려할 수 있다. 외부 정렬 전 예열(프리패스)이나 부분 정렬에도 사용할 수 있다.
Quicksort와 Mergesort는 서브배열 크기가 임계값 이하가 되면 Insertion Sort로 전환하는 하이브리드 구성을 취할 수 있다. 임계값은 일반적으로 16~64 범위에서 실험적으로 채택되며 환경에 따라 달라진다. Bubble Sort의 조기 종료는 데이터가 이미 정렬됐는지 확인하는 검증·안전성 체크 용도로 제한해 쓸 수 있다.
플래시, EEPROM, 원격 메모리처럼 쓰기 비용이 크거나 구조체의 대형 필드를 교환해야 하는 환경에서는 Selection Sort가 스왑 횟수를 최소화한다.
Python 구현
# Python 3.11+, 외부 라이브러리 불필요
from typing import List, TypeVar, Callable
T = TypeVar("T")
def bubble_sort(a: List[T], key: Callable[[T], object] = lambda x: x) -> None:
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if key(a[j]) > key(a[j + 1]):
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 조기 종료
break
def selection_sort(a: List[T], key: Callable[[T], object] = lambda x: x) -> None:
n = len(a)
for i in range(n - 1):
min_i = i
for j in range(i + 1, n):
if key(a[j]) < key(a[min_i]):
min_i = j
if min_i != i:
a[i], a[min_i] = a[min_i], a[i]
def insertion_sort(a: List[T], key: Callable[[T], object] = lambda x: x) -> None:
for i in range(1, len(a)):
cur = a[i]
j = i - 1
kcur = key(cur)
while j >= 0 and key(a[j]) > kcur:
a[j + 1] = a[j]
j -= 1
a[j + 1] = cur
if __name__ == "__main__":
data = [5, 2, 4, 6, 1, 3]
for sort in (bubble_sort, selection_sort, insertion_sort):
arr = data[:]
sort(arr)
print(sort.__name__, arr)선택 시 기대할 수 있는 효과
n ≤ 3264 구간에서는 Insertion Sort가 일반 O(n log n) 정렬보다 1.12.0배 빠른 사례가 빈번하다. 이는 캐시 지역성과 분기 예측에 유리한 조건에서 나타나며, 환경 의존적이므로 최신 정보 확인이 필요하다.
스왑 비용이 큰 시스템에서는 Selection Sort가 교환을 최대 n−1로 제한해 총 쓰기량을 줄이고, 수명과 지연시간 개선에 기여할 수 있다. 구현이 단순해 디버깅과 교육, 코드 리뷰 비용을 낮추는 측면도 있다.
범용 정렬에는 O(n log n) 알고리즘을 사용하되, 서브배열 임계값 이하에서 Insertion Sort로 전환하는 구성이 적합하다. 실제 임계값은 벤치마크와 입력 분포 분석을 바탕으로 환경별로 정해야 한다.