파이썬 버블 정렬(Bubble Sort) 알고리즘: 개념부터 구현, 시간복잡도까지
파이썬 버블 정렬(Bubble Sort) 알고리즘의 개념과 동작 원리, 기본·최적화 구현 코드, 시간복잡도(O(n²))까지 한 번에 정리했습니다. 복붙해서 바로 실행 가능한 예제 포함.
코딩하는 상인 편집부·· 읽기 5분출처 없음파이썬 버블 정렬(Bubble Sort) 알고리즘: 개념부터 구현, 시간복잡도까지
버블 정렬은 정렬 알고리즘을 처음 배울 때 가장 먼저 만나는 알고리즘입니다. 인접한 두 원소를 비교해 자리를 바꾸는 단순한 원리 때문에 이해하기 쉽지만, 그만큼 알아둬야 할 함정과 최적화 포인트도 있습니다.
이 글에서는 버블 정렬의 동작 원리, 파이썬 구현 코드(기본 + 최적화), 시간복잡도, 그리고 언제 쓰면 안 되는지까지 한 번에 정리합니다. 코드는 복사해서 바로 실행할 수 있습니다.
버블 정렬이란?
버블 정렬(Bubble Sort)은 서로 인접한 두 원소를 비교하여, 순서가 잘못되어 있으면 교환하는 과정을 반복하는 정렬 알고리즘입니다.
한 번 순회할 때마다 가장 큰 값이 마치 거품(bubble)이 물 위로 떠오르듯 배열의 맨 끝으로 이동합니다. 이 모습 때문에 "버블" 정렬이라는 이름이 붙었습니다.
핵심 아이디어는 이렇습니다.
- 배열의 처음부터 끝까지 인접한 두 원소를 비교한다.
- 앞이 뒤보다 크면 둘을 교환한다.
- 한 바퀴 돌면 가장 큰 값이 맨 뒤에 고정된다.
- 정렬이 끝날 때까지 이 과정을 반복한다.
동작 과정 한눈에 보기
[5, 3, 8, 1]을 오름차순으로 정렬하는 첫 번째 순회를 따라가 봅시다.
초기: [5, 3, 8, 1]
5 vs 3 → 교환: [3, 5, 8, 1]
5 vs 8 → 유지: [3, 5, 8, 1]
8 vs 1 → 교환: [3, 5, 1, 8] ← 가장 큰 값 8이 맨 뒤로 고정
1차 순회 결과: [3, 5, 1, 8]
이 과정을 배열이 완전히 정렬될 때까지 반복하면, 매 순회마다 끝에서부터 하나씩 정렬이 확정됩니다.
파이썬 기본 구현
가장 직관적인 형태입니다.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # 전체 순회 횟수
for j in range(n - 1 - i): # 이미 정렬된 끝부분 제외
if arr[j] > arr[j + 1]: # 앞이 더 크면
arr[j], arr[j + 1] = arr[j + 1], arr[j] # 교환
return arr
# 사용 예시
nums = [5, 3, 8, 1, 9, 2]
print(bubble_sort(nums)) # [1, 2, 3, 5, 8, 9]
안쪽 반복문의 range(n - 1 - i)가 포인트입니다. 한 바퀴 돌 때마다 맨 뒤 원소는 이미 제자리를 찾았으므로, 다음 순회에서는 그 부분을 비교할 필요가 없습니다.
최적화: 조기 종료(early exit)
기본 구현은 배열이 이미 정렬되어 있어도 끝까지 모든 비교를 수행합니다. 한 번의 순회에서 단 한 번의 교환도 일어나지 않았다면, 배열은 이미 정렬된 상태이므로 즉시 멈춰도 됩니다.
def bubble_sort_optimized(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
이 최적화 덕분에 이미 정렬된 배열에 대해서는 단 한 번의 순회(O(n))만에 끝납니다.
시간복잡도 & 공간복잡도
| 구분 | 복잡도 | 설명 |
|---|---|---|
| 최선 (이미 정렬됨) | O(n) | 조기 종료 적용 시 |
| 평균 | O(n²) | 일반적인 경우 |
| 최악 (역순 정렬) | O(n²) | 모든 쌍을 비교·교환 |
| 공간복잡도 | O(1) | 추가 메모리 없이 제자리 정렬 |
버블 정렬은 비교 횟수가 입력 크기의 제곱에 비례하기 때문에, 데이터가 조금만 커져도 매우 느려집니다. 원소가 1,000개면 약 100만 번, 10,000개면 약 1억 번의 비교가 발생합니다.
버블 정렬의 장단점
장점
- 구현이 매우 단순하고 이해하기 쉽다.
- 추가 메모리가 필요 없는 제자리(in-place) 정렬이다.
- **안정 정렬(stable sort)**이다 — 같은 값의 원소 순서가 보존된다.
단점
- O(n²)의 시간복잡도로 대용량 데이터에 부적합하다.
- 실제 실무에서는 거의 쓰이지 않는다.
다른 정렬 알고리즘과 비교
| 알고리즘 | 평균 시간복잡도 | 안정성 | 특징 |
|---|---|---|---|
| 버블 정렬 | O(n²) | 안정 | 가장 단순, 교육용 |
| 선택 정렬 | O(n²) | 불안정 | 교환 횟수가 적음 |
| 삽입 정렬 | O(n²) | 안정 | 거의 정렬된 데이터에 빠름 |
| 병합 정렬 | O(n log n) | 안정 | 분할 정복, 추가 메모리 필요 |
| 퀵 정렬 | O(n log n) | 불안정 | 평균적으로 가장 빠름 |
실무에서 정렬이 필요하다면 파이썬 내장 함수를 쓰는 것이 정답입니다. 파이썬의 sorted()와 list.sort()는 Timsort(병합 정렬 + 삽입 정렬 혼합)를 사용해 O(n log n)을 보장합니다.
arr = [5, 3, 8, 1]
sorted(arr) # [1, 3, 5, 8] (원본 유지, 새 리스트 반환)
arr.sort() # 원본을 제자리 정렬
자주 묻는 질문
Q. 버블 정렬은 왜 배우나요? 실무에서 직접 쓸 일은 거의 없지만, "인접 원소 비교와 교환"이라는 정렬의 기본 개념을 가장 명확하게 보여주기 때문에 알고리즘 입문용으로 가장 많이 다뤄집니다.
Q. 버블 정렬과 선택 정렬의 차이는? 버블 정렬은 인접한 원소를 계속 교환하며 큰 값을 뒤로 보내고, 선택 정렬은 매번 최솟값을 찾아 앞쪽에 배치합니다. 버블 정렬은 안정 정렬이지만 선택 정렬은 불안정 정렬이라는 점도 차이입니다.
Q. 내림차순으로 정렬하려면?
비교 조건의 부등호 방향만 바꾸면 됩니다. if arr[j] > arr[j + 1]을 if arr[j] < arr[j + 1]로 변경하세요.
마무리
버블 정렬은 효율은 낮지만 정렬의 작동 원리를 이해하는 데 가장 좋은 출발점입니다. 핵심은 "인접한 두 원소를 비교해서 교환한다"는 단순한 규칙과, "교환이 없으면 멈춘다"는 조기 종료 최적화입니다.
실제 코드에서는 항상 파이썬 내장 sorted()를 쓰되, 면접이나 알고리즘 학습에서는 버블 정렬의 동작 원리와 시간복잡도(O(n²))를 정확히 설명할 수 있어야 합니다.
더 다양한 정렬과 알고리즘 템플릿이 필요하다면 [파이썬 알고리즘 치트시트] 글도 함께 확인해보세요.
