[버블 정렬] 하나씩 비교하며 정렬하는 알고리즘

728x90

버블 정렬(Bubble Sort) 

버블 정렬(Bubble Sort)은 정렬 알고리즘 중 가장 단순한 방식으로, 인접한 두 값을 반복적으로 비교하고 필요에 따라 교환하여 정렬을 완성합니다. 이름처럼 큰 값이 점차 리스트 끝으로 ‘버블’처럼 떠오르는 모습에서 유래했습니다. 이 알고리즘은 이해와 구현이 매우 쉬워 알고리즘 학습의 입문 단계에서 자주 사용됩니다. 하지만 효율성 측면에서는 매우 낮기 때문에, 실무에서 사용되는 일은 거의 없습니다.

 

---

1.  버블 정렬이란?

Bubble Sort

 

버블 정렬은 인접한 두 요소를 비교하여 정렬 기준에 맞지 않으면 서로 교환하는 방식을 여러 번 반복하는 정렬 알고리즘입니다. 가장 큰 값이 반복문 한 번마다 맨 뒤로 이동하므로, 전체가 정렬될 때까지 과정을 반복합니다.

작동 방식 (오름차순 기준)

1. 리스트의 첫 번째 요소부터 시작
2. 인접한 두 값을 비교 → 큰 값을 오른쪽으로 이동
3. 한 바퀴 돌면 가장 큰 값이 맨 끝으로 이동
4. 남은 리스트에 대해 반복

장점

• 구현이 매우 간단함
• 개념이 직관적이라 학습용으로 적합
• 제자리(in-place) 알고리즘

단점

• 시간 복잡도가 매우 비효율적 (O(n²))
• 대규모 데이터에는 절대 부적합
• 이미 정렬된 경우를 제외하면 성능 저하 심각

 

---

2.  예시

초기 리스트 :

[5, 3, 8, 4, 2]

첫 번째 :

• 5 > 3 → 교환 → [3, 5, 8, 4, 2]
• 5 < 8 → 그대로
• 8 > 4 → 교환 → [3, 5, 4, 8, 2]
• 8 > 2 → 교환 → [3, 5, 4, 2, 8]

가장 큰 수 8이 맨 뒤로 이동

2회전 :

• 3 < 5 → 그대로
• 5 > 4 → 교환 → [3, 4, 5, 2, 8]
• 5 > 2 → 교환 → [3, 4, 2, 5, 8]

. . .

최종 결과 :

[2, 3, 4, 5, 8]

 

 

---

3.  언어별 구현 예시

a.  Python

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]

b.  C++

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; ++i)
        for (int j = 0; j < n-i-1; ++j)
            if (arr[j] > arr[j+1])
                std::swap(arr[j], arr[j+1]);
}

c.  Java

void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
}

d.  JavaScript

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n - i - 1; j++)
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
}

 

---

4.  시간 복잡도 분석

케이스	시간 복잡도
최악의 경우	O(n²)
평균	O(n²)
최선 (정렬된 상태)	O(n) → 개선 버전에서 가능
공간 복잡도	O(1)
정렬 안정성	안정 정렬

 

---

5.  개선된 버블 정렬

정렬이 더 이상 필요하지 않음을 감지하면, 반복을 중단할 수 있습니다.

def improved_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

 

---

6.  마무리

• 버블 정렬은 가장 단순한 비교 기반 정렬로, 두 요소를 비교 후 필요 시 교환하는 방식입니다.
• 구현이 쉬운 대신 성능은 매우 낮아 학습용 외에는 잘 사용되지 않습니다.
• 개선형 버블 정렬을 통해 약간의 최적화를 할 수 있지만, 여전히 실무에서는 효율적인 알고리즘(퀵, 병합 등)이 선호됩니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Bubble Sort

블로그 글 :

[정렬] 꼭 알아야 할 7가지 정렬 알고리즘 비교 정리

 

---

반응형