버블정렬(Bubble sort)

버블 정렬(Bubble Sort)은 가장 단순하고 직관적인 정렬 알고리즘 중 하나입니다.

이름 그대로, 가장 큰(또는 작은) 값이 마치 거품처럼 리스트 끝으로 올라가는 모습에서 유래된 이름입니다.

---

🔷 1. 버블정렬의 개념

• 인접한 두 값을 비교하여
  • 앞에 있는 값이 더 크면 서로 자리를 바꾸고,
  • 뒤에 있는 값이 더 크면 그대로 둡니다.
• 이 과정을 리스트 끝까지 반복하면서 가장 큰 값을 뒤로 보내고,
• 그런 식으로 전체 리스트를 정렬해 나갑니다.

---

🔷 2. 작동 방식 (정렬 예시)

예를 들어, 다음 리스트를 오름차순으로 정렬한다고 가정합시다.

[5, 3, 8, 4, 2]

🔁 1회전 (가장 큰 수가 맨 뒤로 올라감)

• 5와 3 비교 → 바꿈 → [3, 5, 8, 4, 2]
• 5와 8 비교 → 그대로 → [3, 5, 8, 4, 2]
• 8과 4 비교 → 바꿈 → [3, 5, 4, 8, 2]
• 8과 2 비교 → 바꿈 → [3, 5, 4, 2, 8]

→ 가장 큰 수 8이 맨 뒤로 감

🔁 2회전

• 3과 5 비교 → 그대로
• 5와 4 비교 → 바꿈
• 5와 2 비교 → 바꿈

→ 두 번째로 큰 수 5가 제자리로

🔁 계속 반복...

최종 결과:

[2, 3, 4, 5, 8]

---

🔷 3. 시간 복잡도

케이스	시간 복잡도
최선 (이미 정렬된 경우)	O(n) (개선된 버전에서만)
평균	O(n²)
최악	O(n²)

---

🔷 4. 특징 요약

항목	설명
방식	비교 정렬, 교환 정렬
정렬 방식	제자리(in-place), 안정 정렬
장점	구현이 매우 간단함
단점	느림 (큰 데이터에는 비효율적)

---

🔷 5. 버블정렬이 사용되는 상황

• 알고리즘 수업의 입문용 예제
• 정렬의 기본 구조나 원리를 설명할 때
• 자료 개수가 매우 적을 때

---

버블 정렬 (Bubble Sort) - C++ 구현

📌 전체 코드

#include <iostream>
using namespace std;

// 버블 정렬 함수
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        // 마지막 i개는 이미 정렬되어 있으므로 n-i-1까지만 비교
        for (int j = 0; j < n - i - 1; ++j) {
            // 인접한 두 요소를 비교 후 자리 바꿈
            if (arr[j] > arr[j + 1]) {
                // swap 수행
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 배열 출력 함수
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    // 예시 배열
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "정렬 전 배열: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "정렬 후 배열: ";
    printArray(arr, n);

    return 0;
}

🧾 실행 결과

정렬 전 배열: 5 3 8 4 2
정렬 후 배열: 2 3 4 5 8

📝 설명

• bubbleSort(): 두 중첩 for문을 이용해 인접한 요소를 반복적으로 비교 및 교환합니다.
• printArray(): 배열을 한 줄로 출력해주는 함수입니다.
• 정렬 방식은 오름차순입니다.