거품 정렬 (Bubble Sort)
거품 정렬은 서로 붙어 있는 두 값을 비교해서, 순서가 틀리면 자리를 바꾸는 일을 반복하는 정렬입니다. 정렬 알고리즘 중 가장 직관적인 방법입니다.
한눈에 보기
- 선택 정렬과 비슷한 알고리즘으로, 인접한 두 원소의 크기를 비교하고 조건에 맞지 않으면 자리를 교환하며 정렬합니다.
- 이름은 정렬하는 동안 큰 값이 한 칸씩 뒤로 올라가는 모습이 거품이 수면으로 떠오르는 것 같아서 붙었습니다.
- 비유: 키 순서로 줄을 세울 때, 옆 사람과만 키를 재 보고 더 큰 사람이 뒤로 가는 일을 계속 반복하는 방식입니다. 한 바퀴 돌면 가장 키 큰 사람이 맨 뒤에 섭니다.
- 분류로 보면 값끼리 비교해서 정렬하는 비교 정렬, 같은 값의 원래 순서가 유지되는 안정 정렬, 배열 안에서 자리만 바꾸는 제자리 정렬입니다.
동작 과정
오름차순 정렬 기준입니다.
- 1회전에서 첫 번째와 두 번째 원소, 두 번째와 세 번째 원소, 세 번째와 네 번째 원소, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소까지 비교하고, 순서가 맞지 않으면 서로 교환합니다.
- 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동합니다. 그래서 2회전에서는 맨 끝 원소를 빼고 비교하고, 2회전이 끝나면 끝에서 두 번째 원소까지 제외합니다. 이렇게 1회전마다 정렬에서 제외되는 원소가 하나씩 늘어납니다.
예시 배열 [4, 2, 5, 1]로 따라가 보겠습니다.
| 회전 | 비교하는 두 값 | 배열 상태 | 설명 |
|---|---|---|---|
| 시작 | - | [4, 2, 5, 1] | 처음 상태 |
| 1회전 | 4, 2 | [2, 4, 5, 1] | 4가 더 크므로 교환 |
| 1회전 | 4, 5 | [2, 4, 5, 1] | 순서가 맞으므로 그대로 |
| 1회전 | 5, 1 | [2, 4, 1, 5] | 교환. 가장 큰 5가 맨 뒤에 확정 |
| 2회전 | 2, 4 | [2, 4, 1, 5] | 그대로 |
| 2회전 | 4, 1 | [2, 1, 4, 5] | 교환. 4 확정 |
| 3회전 | 2, 1 | [1, 2, 4, 5] | 교환. 정렬 완료 |
그림으로 보기
그림 출처: GimunLee/tech-refrigerator (Apache-2.0)
Python 코드
python
def bubble_sort(arr):
"""인접한 두 값을 비교해 큰 값을 뒤로 보내는 거품 정렬 (오름차순)"""
n = len(arr)
for i in range(n - 1): # 1.
for j in range(1, n - i): # 2.
if arr[j - 1] > arr[j]: # 3.
arr[j - 1], arr[j] = arr[j], arr[j - 1]
return arr
print(bubble_sort([4, 2, 5, 1]))
# 출력: [1, 2, 4, 5]i는 이미 뒤쪽에 확정되어 정렬에서 제외된 원소의 개수입니다. 1회전이 끝날 때마다 배열 마지막 자리에 가장 큰 원소가 오므로 하나씩 늘려 줍니다. 마지막 한 개는 비교할 상대가 없으므로n - 1회전이면 충분합니다.- 비교할 위치를 고르는 반복문입니다.
j는 현재 원소,j - 1은 바로 앞 원소를 가리키므로j는 1부터 시작합니다. 뒤에서i개는 이미 확정이라n - i전까지만 봅니다. - 두 원소의 크기를 비교합니다. 오름차순이므로 앞 원소가 더 크면 앞 원소가 뒤로 가야 하니 서로 자리를 바꿉니다. Python은
a, b = b, a한 줄로 교환할 수 있습니다.
개선된 거품 정렬
원문은 "개선된 거품 정렬도 있지만 기초 학습이므로 넘어간다"고 했습니다. 개선 아이디어는 간단합니다. 한 회전 동안 교환이 한 번도 없었다면 이미 정렬이 끝난 것이니 바로 멈추면 됩니다.
python
def bubble_sort_early_exit(arr):
"""교환이 없으면 일찍 멈추는 거품 정렬"""
n = len(arr)
for i in range(n - 1):
swapped = False # 1.
for j in range(1, n - i):
if arr[j - 1] > arr[j]:
arr[j - 1], arr[j] = arr[j], arr[j - 1]
swapped = True # 2.
if not swapped: # 3.
break
return arr
print(bubble_sort_early_exit([1, 2, 3, 5, 4]))
# 출력: [1, 2, 3, 4, 5]- 이번 회전에서 교환이 있었는지 기록할 표시입니다.
- 한 번이라도 교환하면
True로 바꿉니다. - 한 회전을 다 돌았는데 교환이 없었다면 모든 이웃이 이미 순서대로라는 뜻이므로 반복을 끝냅니다.
시간복잡도와 공간복잡도
비교 횟수는 (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2이므로 O(n²) 입니다. 기본 거품 정렬은 배열이 이미 정렬되어 있든 아니든 모든 이웃 쌍을 똑같이 비교하기 때문에 최선, 평균, 최악이 모두 O(n²)입니다. (시간 복잡도 글에서 O 표기법을 먼저 보면 이해가 쉽습니다.)
| 경우 | 기본 거품 정렬 | 개선된 거품 정렬 |
|---|---|---|
| 최선 (이미 정렬됨) | O(n²) | O(n) |
| 평균 | O(n²) | O(n²) |
| 최악 (거꾸로 정렬됨) | O(n²) | O(n²) |
| 공간 | 추가 메모리 O(1) (입력 포함 O(n)) | 추가 메모리 O(1) (입력 포함 O(n)) |
- 개선판은 이미 정렬된 배열이면 1회전(n-1번 비교)만에 멈추므로 최선이 O(n)이 됩니다.
- 공간: 주어진 배열 안에서 교환만 하므로, 입력 배열 말고 추가로 드는 메모리는 교환용 변수 정도인 O(1)입니다.
장점과 단점
장점
- 구현이 매우 간단하고 코드가 직관적입니다.
- 정렬할 배열 안에서 교환하는 방식이라 다른 메모리 공간이 필요 없습니다. → 제자리 정렬(in-place sorting)
- 안정 정렬(Stable Sort)입니다. 앞 값이 더 클 때만 교환하므로 같은 값끼리는 순서가 바뀌지 않습니다.
단점
- 기본형은 최선, 평균, 최악 모두 O(n²)라서 매우 비효율적입니다.
- 정렬되지 않은 원소가 제자리로 가려면 한 칸씩 이동해야 하므로 교환(swap)이 많이 일어납니다.
마무리
정렬 알고리즘 중 가장 직관적인 거품 정렬을 알아봤습니다. 기술 면접에서도 종종 나오는 정렬이라 알아 두면 좋습니다. 교환 횟수를 줄인 선택 정렬과 비교해서 보면 차이가 잘 보입니다.
정리
| 개념 | 비전공자 버전 요약 |
|---|---|
| 거품 정렬 | 옆 친구와 비교해 큰 값을 뒤로 보내기 반복 |
| 1회전의 결과 | 한 바퀴 돌 때마다 가장 큰 값이 맨 뒤에 확정 |
| 개선된 거품 정렬 | 한 바퀴 동안 자리 바꿈이 없으면 바로 끝내기 |
| 안정 정렬 | 같은 값끼리는 원래 순서 그대로 |
출처: GimunLee/tech-refrigerator (Apache-2.0), 코드는 Python으로 다시 작성