버블 정렬(Bubble Sort) 알고리즘이란?

버블 정렬(Bubble Sort) 알고리즘이란?

버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 리스트를 반복적으로 순회하면서 인접한 두 요소를 비교하고, 잘못된 순서라면 교환하여 정렬을 수행합니다. 가장 큰 값이 "거품처럼" 위로 올라오는 모습을 떠올리면 이해하기 쉽습니다.

버블 정렬의 작동 원리

1. 첫 번째 요소와 두 번째 요소를 비교: 첫 번째 요소가 두 번째 요소보다 크면, 두 요소를 교환합니다.
2. 두 번째 요소와 세 번째 요소를 비교: 두 번째 요소가 세 번째 요소보다 크면, 두 요소를 교환합니다.
3. 리스트 끝까지 반복: 리스트의 끝까지 이 과정을 반복합니다. 한 번의 전체 순회가 끝나면 가장 큰 요소가 리스트의 끝으로 이동합니다.
4. 반복: 리스트 전체가 정렬될 때까지 이 과정을 반복합니다.

버블 정렬의 단계별 예시

리스트 [5, 1, 4, 2, 8]을 버블 정렬로 정렬하는 과정을 살펴보겠습니다.

첫 번째 패스

• (5, 1) 비교 -> 교환 (1, 5, 4, 2, 8)

• (5, 4) 비교 -> 교환 (1, 4, 5, 2, 8)

• (5, 2) 비교 -> 교환 (1, 4, 2, 5, 8)

• (5, 8) 비교 -> 교환 없음 (1, 4, 2, 5, 8)

두 번째 패스

• (1, 4) 비교 -> 교환 없음 (1, 4, 2, 5, 8)

• (4, 2) 비교 -> 교환 (1, 2, 4, 5, 8)

• (4, 5) 비교 -> 교환 없음 (1, 2, 4, 5, 8)

세 번째 패스

• (1, 2) 비교 -> 교환 없음 (1, 2, 4, 5, 8)

• (2, 4) 비교 -> 교환 없음 (1, 2, 4, 5, 8)

[완료!]

리스트가 정렬되었으므로 알고리즘이 종료됩니다.

버블 정렬의 시간 복잡도

버블 정렬의 시간 복잡도는 최악, 최선, 평균의 경우 모두 O(n^2)입니다. 리스트의 길이가 길어질수록 정렬에 걸리는 시간이 기하급수적으로 증가합니다. 따라서 버블 정렬은 작은 데이터셋에 대해서만 효율적입니다.

• 최악의 경우 시간 복잡도: O(n^2)
• 최선의 경우 시간 복잡도: O(n^2) (개선된 버전에서는 O(n))
• 평균 시간 복잡도: O(n^2)
• 공간 복잡도: O(1) (제자리 정렬 알고리즘)

파이썬으로 버블 정렬 구현

def bubble_sort(arr):
   n = len(arr)
   for i in range(n):
       # 마지막 i개 요소는 이미 정렬되어 있으므로 반복할 필요가 없음
       for j in range(0, n-i-1):
           # 인접한 두 요소를 비교하고 필요하면 교환
           if arr[j] > arr[j+1]:
               arr[j], arr[j+1] = arr[j+1], arr[j]

# 예제 리스트
numbers = [64, 34, 25, 12, 22, 11, 90]

# 버블 정렬 수행
bubble_sort(numbers)

# 정렬된 리스트 출력
print(numbers)  # 출력: [11, 12, 22, 25, 34, 64, 90]

요약

• 버블 정렬: 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 요소를 비교하고 필요 시 교환하는 방식으로 정렬을 수행.
• 시간 복잡도: 최악, 최선, 평균 모두 O(n^2).
• 작동 원리: 리스트를 반복적으로 순회하면서 인접한 요소를 비교하고, 잘못된 순서라면 교환하여 정렬.
• 공간 복잡도: O(1) (제자리 정렬).

버블 정렬은 이해하기 쉽고 구현이 간단하지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 성능이 떨어집니다. 따라서 실무에서는 데이터가 적을 때나 학습용으로 주로 사용됩니다.