버블 정렬(Bubble Sort) 알고리즘

버블 정렬(Bubble Sort) 알고리즘은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다. 선택 정렬(Selection Sort)과 기본 개념이 유사하지만, 매 회전(iteration)마다 가장 큰 값이 배열의 끝으로 이동한다는 특징이 있습니다.

버블 정렬 알고리즘의 개념

---

버블 정렬은 배열의 첫 번째 요소와 두 번째 요소를 비교하고, 두 번째 요소와 세 번째 요소를 비교하는 방식으로 진행됩니다. 각 비교에서 두 요소를 교환하여 큰 값이 뒤로 이동하게 됩니다. 이렇게 한 회전(iteration)을 수행하면 가장 큰 값이 배열의 끝에 위치하게 됩니다.

각 회전을 반복할 때마다 배열의 끝에서부터 하나씩 정렬된 요소가 제외되며, 정렬되지 않은 나머지 부분에 대해서만 비교를 계속합니다. 이 과정을 반복하여 배열 전체가 정렬됩니다.

예시

다음과 같은 배열이 있다고 가정합시다:

| 4 | 1 | 3 | 2 |

이 배열을 버블 정렬 알고리즘으로 오름차순으로 정렬한다면, 다음과 같이 진행됩니다.

1. 첫 번째 회전:

   • | 4 | 1 | 3 | 2 | → | 1 | 4 | 3 | 2 | → | 1 | 3 | 4 | 2 | → | 1 | 3 | 2 | 4 |
   • 첫 번째 회전 결과: | 1 | 3 | 2 | 4 |

2. 두 번째 회전:

   • | 1 | 3 | 2 | 4 | → | 1 | 3 | 2 | 4 | → | 1 | 2 | 3 | 4 |
   • 두 번째 회전 결과: | 1 | 2 | 3 | 4 |
   • 정렬 완료

이처럼 버블 정렬은 비교와 교환을 반복하며 배열을 정렬합니다.

버블 정렬 알고리즘의 구현

---

C언어로 버블 정렬 알고리즘을 구현한 코드는 다음과 같습니다.

#include <stdio.h>

void bubble_sort(int ary[], int n) {
    int temp;
    
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            if (ary[j] > ary[j + 1]) {  // 오름차순 정렬
                temp = ary[j];
                ary[j] = ary[j + 1];
                ary[j + 1] = temp;
            }
        }
    }
}

int main(void) {
    int n;
    scanf("%d", &n); // 배열의 크기 입력받기

    int ary[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &ary[i]); // 배열 요소 입력받기
    }
    
    bubble_sort(ary, n); // 입력받은 배열을 버블 정렬

    for (int i = 0; i < n; i++) { // 정렬된 배열 출력
        printf("%d\n", ary[i]);
    }

    return 0;
}

위 코드에서는 bubble_sort 함수가 배열 ary를 오름차순으로 정렬합니다. 배열의 크기 n을 입력받아, 배열의 각 요소를 입력받은 후, 버블 정렬 알고리즘을 적용하여 정렬된 결과를 출력합니다.

버블 정렬 알고리즘 특징

---

장점 :

• 구현이 매우 간단하여 이해하기 쉽습니다.

• 정렬이 이미 거의 완료된 경우에는 상대적으로 효율적일 수 있습니다.

단점 :

• 시간 복잡도가 O(n^2)로, 배열의 크기가 커질수록 비효율적입니다.

• 매 회전마다 교환 작업(SWAP)이 빈번히 발생하므로, 교환에 따른 연산 비용이 클 수 있습니다.

• 배열이 이미 정렬된 경우에도 비교 작업이 계속 수행되므로 불필요한 작업이 발생할 수 있습니다.

버블 정렬 알고리즘의 시간 복잡도

---

버블 정렬 알고리즘의 시간 복잡도는 다음과 같습니다:

• 비교 횟수 :
  • 최상, 평균, 최악의 경우 모두 동일하게 n-1, n-2, ..., 2, 1 번의 비교가 필요하며, 이는 총 n(n-1)/2 번의 비교를 의미합니다.
• 교환 횟수 :
  • 입력 자료가 역순으로 정렬된 최악의 경우, 한 번의 교환을 위해 3번의 이동(스왑 작업)이 필요하며, 총 3n(n-1)/2 번의 교환이 발생합니다.
  • 입력 자료가 이미 정렬된 최상의 경우, 교환 작업이 발생하지 않습니다.

결국, 버블 정렬의 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(n^2)로 동일합니다. 따라서, 작은 크기의 배열에서는 사용 가능하지만, 큰 배열에서는 비효율적인 알고리즘입니다.