Bubble Sort: 인접한 두 원소를 비교하며 정렬하는 가장 간단한 정렬 알고리즘
Bubble Sort는 배열의 처음부터 끝까지 반복하며, 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 큰 요소가 거품처럼 배열의 끝으로 이동하는 특징을 가지고 있습니다. 구현이 간단하지만, 성능이 좋지 않아 대규모 데이터셋에는 적합하지 않습니다.
1. 개념
Bubble Sort(버블 정렬)는 비교 정렬(Comparison Sort)의 한 종류입니다. 배열의 각 요소를 순차적으로 비교하여, 정렬 기준(오름차순 또는 내림차순)에 맞지 않는 요소들을 교환하며 정렬합니다. 이름처럼 큰 값(또는 작은 값)이 마치 거품처럼 배열의 끝으로 점점 더 이동하는 모습을 보입니다.
2. 왜 사용하는가
Bubble Sort는 구현이 매우 간단하기 때문에, 정렬 알고리즘의 기본적인 개념을 이해하는 데 용이합니다. 하지만 성능이 좋지 않아 실무에서는 거의 사용되지 않습니다. 주로 교육적인 목적으로 사용되거나, 매우 작은 데이터셋을 정렬할 때 제한적으로 사용될 수 있습니다.
3. 동작 원리
- 배열의 첫 번째 요소부터 시작하여, 다음 요소와 비교합니다.
- 만약 두 요소의 순서가 정렬 기준에 맞지 않으면, 두 요소의 위치를 교환합니다.
- 배열의 끝까지 위 과정을 반복합니다. 이 과정을 'pass'라고 합니다.
- 첫 번째 pass가 완료되면, 가장 큰 요소(또는 가장 작은 요소)가 배열의 맨 끝에 위치하게 됩니다.
- 배열의 끝에서부터 두 번째 요소까지 반복합니다.
- 위 과정을 배열의 모든 요소가 정렬될 때까지 반복합니다.
4. 코드 예제
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 예시
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print(sorted_arr) # 출력: [11, 12, 22, 25, 34, 64, 90]5. 시간 복잡도 또는 성능 특성
- 최선의 경우: O(n) - 배열이 이미 정렬된 경우 (한 번의 pass만 수행)
- 평균의 경우: O(n^2)
- 최악의 경우: O(n^2) - 배열이 역순으로 정렬된 경우
- 공간 복잡도: O(1) - 제자리 정렬(in-place sort) 알고리즘 (별도의 추가 공간을 사용하지 않음)
6. 실무 사용 사례
Bubble Sort는 실무에서 거의 사용되지 않습니다. 하지만, 정렬 알고리즘을 처음 배우는 학생이나, 간단한 정렬 로직을 구현해야 하는 경우에 활용될 수 있습니다. 예를 들어, 매우 작은 데이터셋을 정렬하거나, 테스트용 데이터 생성에 사용될 수 있습니다.
7. 주의할 점
- Bubble Sort는 성능이 좋지 않으므로, 대규모 데이터셋에는 사용하지 않아야 합니다.
- 이미 정렬된 배열의 경우, 최선의 경우 O(n)의 시간 복잡도를 가지지만, 일반적으로는 O(n^2)의 시간 복잡도를 가집니다.
- 제자리 정렬 알고리즘이므로, 별도의 추가 공간을 사용하지 않지만, 교환 연산이 많이 발생하므로 메모리 접근 비용이 증가할 수 있습니다.
8. 핵심 정리
Bubble Sort는 구현이 간단하지만 성능이 좋지 않은 정렬 알고리즘입니다. 기본적인 정렬 알고리즘의 원리를 이해하는 데 도움이 되지만, 실무에서는 거의 사용되지 않습니다. 성능이 중요한 경우에는 다른 정렬 알고리즘(Quick Sort, Merge Sort 등)을 사용하는 것이 좋습니다.