버블 정렬 (Bubble Sort) (C++)

버블 정렬 (Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나. 인접한 두 데이터를 비교하여 크기 순서에 맞지 않으면 자리를 바꾸는 방식으로, 가장 큰 값(또는 가장 작은 값)이 거품처럼 배열의 끝으로 올라간다고 해서 버블 정렬이라고 불린다.

---

동작 원리

1. 배열의 첫 번째 요소부터 시작하여 인접한 두 값을 비교.
2. 두 값이 정렬 기준(오름차순 또는 내림차순)에 맞지 않으면 교환(swap).
3. 한 번의 반복이 끝나면 가장 큰 값(또는 가장 작은 값)이 배열의 맨 끝에 위치.
4. 위 과정을 배열의 크기만큼 반복하며, 매번 비교 범위는 하나씩 줄어든다.

---

특징

• 시간 복잡도:
  • 최악/평균: O(n^2)
  • 최선 (이미 정렬된 경우): O(n)
• 공간 복잡도: O(1) (추가 메모리 사용 없음)
• 안정적 정렬: 값이 같을 경우 원래의 순서가 유지.
• 효율성: 비효율적이라 실제 응용보다는 학습 목적으로 많이 사용.

---

예제 코드 (C++)

오름차순 버블 정렬 구현

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;  // 교환 여부를 확인하기 위한 플래그
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {  // 오름차순: 왼쪽 값이 크면 교환
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // 교환이 없으면 이미 정렬된 상태
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    cout << "정렬 전 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    bubbleSort(arr);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

---

코드 설명

1. for 루프:
   • 첫 번째 for 루프: 배열의 끝까지 반복.
   • 두 번째 for 루프: 매번 정렬 범위를 줄이며 인접한 값을 비교.
2. swap 함수:
   • 두 값을 교환합니다. C++ 표준 라이브러리에 포함된 함수로, 성능이 좋습니다.
3. swapped 플래그:
   • 한 번의 반복 동안 교환이 발생하지 않았다면 배열이 이미 정렬된 상태이므로, 루프를 조기에 종료합니다. 이는 최선의 경우 시간 복잡도를 O(n)로 줄이는 역할을 합니다.

---

예제 동작 과정

입력 배열: [64, 34, 25, 12, 22, 11, 90]

1. 첫 번째 패스:
   • 비교: 64 > 34 → 교환 → [34, 64, 25, 12, 22, 11, 90]
   • 비교: 64 > 25 → 교환 → [34, 25, 64, 12, 22, 11, 90]
   • 비교: 64 > 12 → 교환 → [34, 25, 12, 64, 22, 11, 90]
   • 비교: 64 > 22 → 교환 → [34, 25, 12, 22, 64, 11, 90]
   • 비교: 64 > 11 → 교환 → [34, 25, 12, 22, 11, 64, 90]
   • 비교: 64 < 90 → 교환 없음.
   • 결과: [34, 25, 12, 22, 11, 64, 90]
2. 두 번째 패스:
   • 비교: 34 > 25 → 교환 → [25, 34, 12, 22, 11, 64, 90]
   • 비교: 34 > 12 → 교환 → [25, 12, 34, 22, 11, 64, 90]
   • 비교: 34 > 22 → 교환 → [25, 12, 22, 34, 11, 64, 90]
   • 비교: 34 > 11 → 교환 → [25, 12, 22, 11, 34, 64, 90]
   • 결과: [25, 12, 22, 11, 34, 64, 90]
3. 세 번째 패스:
   • 비교: 25 > 12 → 교환 → [12, 25, 22, 11, 34, 64, 90]
   • 비교: 25 > 22 → 교환 → [12, 22, 25, 11, 34, 64, 90]
   • 비교: 25 > 11 → 교환 → [12, 22, 11, 25, 34, 64, 90]
   • 결과: [12, 22, 11, 25, 34, 64, 90]
4. 네 번째 패스:
   • 비교: 12 > 22 → 교환 없음.
   • 비교: 22 > 11 → 교환 → [12, 11, 22, 25, 34, 64, 90]
   • 결과: [12, 11, 22, 25, 34, 64, 90]
5. 다섯 번째 패스:
   • 비교: 12 > 11 → 교환 → [11, 12, 22, 25, 34, 64, 90]
   • 결과: [11, 12, 22, 25, 34, 64, 90]
6. 이후 추가 패스에서는 교환이 발생하지 않으므로 종료.

---

장점과 단점

장점

• 구현이 간단하며, 코드 작성이 쉽다.
• 이미 정렬된 데이터에 대해서는 효율적으로 작동(최선: O(n)).

단점

• O(n^2)의 시간 복잡도로, 대규모 데이터에 적합하지 않다.
• 교환 연산이 많아 상대적으로 느림.

---