# 버블·선택·삽입 정렬, 동작 원리와 실무 선택 기준

- 게시: 2026.07.21
- 원문(HTML): https://trendbrief.news/articles/bubble-selection-insertion-sort-comparison.html
- 발행: [트렌드브리프](https://trendbrief.news/)

![버블·선택·삽입 정렬, 동작 원리와 실무 선택 기준](https://trendbrief.news/assets/articles/%EB%B2%84%EB%B8%94-%EC%84%A0%ED%83%9D-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-%EB%8F%99%EC%9E%91-%EC%9B%90%EB%A6%AC%EC%99%80-%EC%8B%A4%EB%AC%B4-%EC%84%A0%ED%83%9D-%EA%B8%B0%EC%A4%80/hero-auto.png)

> 버블·선택·삽입 정렬은 모두 평균 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²)다. 둘째, 멀리 떨어진 값을 통째로 맞바꾸는 과정에서 같은 값의 상대 순서가 뒤집힐 수 있어 일반적인 구현은 불안정하다. 순서가 중요한 데이터를 다룬다면 이 점을 반드시 확인해야 한다.

![높이가 다른 막대들이 늘어선 가운데 인접한 두 막대가 강조돼 스왑 화살표로 연결되고, 오른쪽 끝 큰 막대 둘은 정렬 완료로 표시된 선화 일러스트](https://trendbrief.news/assets/articles/%EB%B2%84%EB%B8%94-%EC%84%A0%ED%83%9D-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-%EB%8F%99%EC%9E%91-%EC%9B%90%EB%A6%AC%EC%99%80-%EC%8B%A4%EB%AC%B4-%EC%84%A0%ED%83%9D-%EA%B8%B0%EC%A4%80/sec-ch4.jpg)

이웃한 둘을 견주어 자리를 바꾸는 것 — 비교 기반 정렬의 한 걸음이 여기서 시작한다.

## 삽입 정렬: 정렬된 앞부분에 끼워 넣기

삽입 정렬은 배열의 두 번째 원소부터 시작해, 그 값을 왼쪽의 이미 정렬된 부분에서 알맞은 자리에 끼워 넣는다. 끼워 넣을 자리를 찾는 동안 그보다 큰 값들은 오른쪽으로 한 칸씩 민다. 카드 게임에서 손에 든 패를 하나씩 제자리에 꽂아 정렬하는 방식과 같다.

```
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](https://github.com/python/cpython/blob/main/Objects/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개 미만 | 인트로 정렬(퀵+힙) |

세 임계값이 서로 다른 것은 언어와 자료형, 벤치마크 환경이 다르기 때문이며 모두 실험으로 정한 경험적 값이다. 파이썬 공식 [정렬 문서](https://docs.python.org/3/howto/sorting.html)에서 확인할 수 있듯 파이썬의 기본 정렬은 안정 정렬인데, 그 바탕에 안정 정렬인 삽입 정렬이 깔려 있는 것도 우연이 아니다. 빅오 표기만으로 실제 성능을 판단할 수 없고 상수 항과 부가 비용까지 따져야 한다는 이 관점은, [리플렉션처럼 런타임에 타입을 다루는 기능](https://trendbrief.news/articles/programming-reflection-runtime-types-performance-cost.html)의 성능 대가를 따질 때도 똑같이 필요하다. 정리하면 삽입 정렬은 단독 알고리즘으로는 느리지만, 빠른 알고리즘의 마지막 단계를 채우는 부품으로 지금도 현역이다.

## 어떤 상황에 무엇을 고를까

세 알고리즘 중 실무에서 직접 손으로 쓸 일이 있다면 대부분 삽입 정렬이다. 판단 기준을 정리하면 다음과 같다.

- 거의 정렬된 데이터를 다듬을 때는 삽입 정렬이 낫다. 로그처럼 대체로 시간순인데 일부만 어긋난 데이터, 또는 이미 정렬된 목록에 소수의 새 항목이 추가된 경우 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번을 넘어 쓰기 최소화라는 장점이 사라진다. 한 단계에서는 최솟값의 위치만 기억해 두었다가 단계 끝에서 한 번만 교환한다.

## 관련 글

- [그래프 탐색 BFS와 DFS, 큐와 스택으로 갈리는 선택 기준](https://trendbrief.news/articles/graph-traversal-bfs-vs-dfs.md)
- [사내 지식베이스 구축, 세 가지 방식과 도구 선택 기준](https://trendbrief.news/articles/internal-knowledge-base-three-approaches-tools.md)
- [추상 구문 트리(AST), 코드를 트리로 다루는 원리와 실무 도구](https://trendbrief.news/articles/abstract-syntax-tree-ast-principles-tools.md)
- [재귀 함수와 분할 정복, 문제를 쪼개는 원리와 비용 계산](https://trendbrief.news/articles/recursion-divide-and-conquer-cost-analysis.md)
- [스택과 큐, LIFO·FIFO 차이와 실무 쓰임새](https://trendbrief.news/articles/stack-vs-queue-lifo-fifo-differences.md)