버블 정렬

5.1 버블 정렬 정의

버블 정렬 (Bubble Sort) — 이건 아주 간단한 정렬 알고리즘이야. 리스트를 여러 번 순회하면서 인접한 요소들을 비교하고, 만약 순서가 잘못되었으면 서로 교환해. 이 프로세스는 리스트가 완전히 정렬될 때까지 지속돼.

작동 원리:

1. 알고리즘이 리스트를 순회하면서 모든 인접한 요소 쌍을 비교해.
2. 요소들이 잘못된 순서에 있을 경우 (오름차순 정렬일 때 첫 번째 요소가 두 번째보다 클 때) — 서로 교환해.
3. 이 프로세스를 리스트의 모든 요소 쌍에 대해 반복해.
4. 전체 순회가 끝나면 가장 큰 요소가 자신의 자리에 '떠오르게 돼' (물 표면의 거품처럼), 그래서 다음 순회에서는 더 이상 참여하지 않아도 돼.
5. 리스트가 정렬될 때까지 이 과정을 반복해.

버블 정렬의 시간 및 공간 복잡도

시간 복잡도:

• 최악의 경우: O(n^2) — 요소들이 처음에 역순으로 정렬되어 있을 때 발생해.
• 평균의 경우: O(n^2) — 요소들이 랜덤으로 배열되어 있을 때 발생해.
• 최고의 경우: O(n) — 요소들이 이미 정렬되어 있을 때 발생해 (여기서 알고리즘은 교환이 발생했는지 검사하는 최적화를 추가할 수 있어).

공간 복잡도:

O(1) — 알고리즘이 추가적인 메모리를 거의 사용하지 않기 때문에 (일시적인 값들을 저장하기 위한 몇 개의 변수만 필요해).

5.2 알고리즘 구현

'버블 정렬' 알고리즘은 가장 간단하고 기본적인 정렬 알고리즘이야. 단순히 요소를 짝지어 비교하고 필요시 위치를 바꾸는 거야.

버전 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # 요소 교환

print("정렬된 배열:", array)
# 출력: 정렬된 배열: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

내부 루프 (초록색으로 강조됨)는 요소를 오른쪽 이웃과 비교해. 그리고 필요하다면 위치를 바꿔.

버전 2:

첫 번째 순회 후에 가장 큰 요소가 가장 오른쪽에 위치하게 되니까, 다음 순회에서는 이 요소를 고려하지 않아도 돼.

두 번째 순회 후에는 오른쪽에 최대 두 개의 큰 요소가 있게 되니까, 내부 루프는 n - 1까지가 아니라 n - 1 - i까지 진행해. 여기서 i는 외부 루프의 진행된 횟수를 의미해.

새 버전은 이렇게 생겼어:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]  # 요소 교환

print("정렬된 배열:", array)
# 출력: 정렬된 배열: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

버전 3:

배열이 이미 거의 정렬되어 있을 수도 있어. 그래서 이런 최적화를 추가할 수 있어: 만약 내부 루프가 모든 요소를 순회했지만 단 하나의 교환도 없었다면, 정렬이 완료된 거야.

이번 버전에서는 swapped 변수로 마지막 순회에서 요소의 교환이 발생했는지를 추적해. 만약 배열을 순회한 후 교환이 하나도 발생하지 않았다면, 배열은 이미 정렬된 상태라는 것을 의미하고, 추가적인 순회를 수행하는 것은 의미가 없어 — 이건 정렬에 도움이 되지 않거든. 따라서, swapped 변수는 거의 정렬된 배열에서 알고리즘의 실행을 크게 빠르게 해줘, 조기 종료하면서 말이지.

Python에서의 버블 정렬 구현:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False  # 최적화: 교환이 발생했는지 검사
        for j in range(0, n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]  # 요소 교환
                swapped = True
        if not swapped:
            break  # 교환이 없었다면, 배열은 이미 정렬된 상태
    return array

# 사용 예제:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("정렬된 배열:", sorted_array)
# 출력: 정렬된 배열: [11, 12, 22, 25, 34, 64, 90]