[알고리즘] 정렬 | 버블 정렬

버블 정렬 🫧

버블 정렬은 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 한다.

마치 물속에서 거품이 천천히 위로 떠오르듯이, 가장 큰 값이 한 단계씩 맨 뒤로 이동하는 모습에서 ‘버블(Bubble)’이라는 이름이 붙었다고 한다.

버블 정렬 원리

버블 정렬의 핵심 동작은 다음과 같다.

1. 리스트의 첫 번째 원소부터 이웃한 두 원소를 비교합니다.
2. 왼쪽 원소가 오른쪽 원소보다 크다면 위치를 교환합니다.
3. 리스트의 끝까지 반복하여 가장 큰 값이 맨 뒤로 이동합니다.
4. 이후 정렬된 부분을 제외하고 다시 반복합니다.

---

📌 예시

초기 배열:

6	4	3	9	7

1번째 패스:

1. (6, 4) 비교 → 교환
   | 4 | 6 | 3 | 9 | 7 |
2. (6, 3) 비교 → 교환
   | 4 | 3 | 6 | 9 | 7 |
3. (6, 9) 비교 → 그대로
   | 4 | 3 | 6 | 9 | 7 |
4. (9, 7) 비교 → 교환
   | 4 | 3 | 6 | 7 | 9 |
   → 9가 맨 뒤로 이동

2번째 패스:

1. (4, 3) 비교 → 교환
   | 3 | 4 | 6 | 7 | 9 |
2. (4, 6) 비교 → 그대로
   | 3 | 4 | 6 | 7 | 9 |
3. (6, 7) 비교 → 그대로
   | 3 | 4 | 6 | 7 | 9 |
   → 7이 제자리를 찾음

3번째 패스:

1. (3, 4) 비교 → 그대로
2. (4, 6) 비교 → 그대로
   → 6도 자리 고정

최종 정렬된 배열:

3	4	6	7	9

---

특징 및 시간 복잡도

• 한 번의 패스마다 가장 큰 값이 오른쪽으로 이동한다.
• 총 n-1 패스가 필요하며, 각 패스마다 비교 횟수가 줄어든다.
• 비교 횟수 총합:

  (n-1) + (n-2) + … + 1 = n(n-1)/2
  따라서 시간 복잡도는 O(n²) 이다

---

버블 정렬 장단점

장점

• 구현이 매우 간단하고 직관적이다.
• 배열이 이미 거의 정렬된 경우, 빠르게 종료할 수 있다. (조기 종료 조건 추가 시)
• 추가 메모리가 거의 필요 없는 in-place 정렬입니다.

  in-place 정렬이란?
  - 배열 안에서 자리만 바꿔가며 정렬하는 것 = in-place
  - 정렬할 때 새로운 배열이나 리스트를 따로 만들지 않는 것

단점

• 비교 및 교환 횟수가 많아 속도가 느리다. (O(n²))
• 대규모 데이터에서는 매우 비효율적이다.
• 대부분의 경우 삽입 정렬, 퀵 정렬 같은 다른 알고리즘보다 성능이 낮다.

---

버블 정렬 파이썬 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 각 패스마다 교환이 발생했는지 체크
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                # 교환
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # 만약 교환이 없었다면 이미 정렬된 상태
        if not swapped:
            break
    return arr

# 사용 예시
arr = [6, 4, 3, 9, 7]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # 출력: [3, 4, 6, 7, 9]

---