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

버블 정렬(Bubble Sort)

버블 정렬은 인접한 원소 간의 대소관계를 비교하여 주어진 규칙에 따라 인접한 원소를 교환하는 방법입니다. 맨 앞에 위치한 원소부터 순차적으로 인접한 원소 간의 대소관계를 비교하면, 배열의 원소 중 가장 큰 값이 마지막에 위치하게 됩니다. 이를 통해 마지막 원소가 정렬이 되고, 이를 N-1 번 반복을 하게 되면 정렬이 완료 됩니다.

버블 정렬의 시간복잡도는 고려해야 할 반복문이 (정렬해야 할 원소의 개수 - 1) * (최대 교환 수)이므로 총 O(N^2)가 됩니다. 앞 글에서 설명한 선택 정렬과 삽입 정렬과 동일한 시간복잡도 이므로 자주 쓰이지는 않습니다.

아래는 버블 정렬의 이해를 도울 수 있는 의사코드와 예제를 보여 줍니다.

의사코드

bubbleSort(){
    ary[SIZE]
    for i = 1 to SIZE{
        for j = 1 to SIZE-i{
               if(ary[j-1] > ary[j])
                swap(ary[j-1], ary[j])
        }
    }
}

예제

-입력

첫 번째 줄에는 정렬할 원소의 수 N

두 번째 줄에는 N크기의 배열을 갖는 원소 값

-출력

버블 정렬이 수행된 배열의 값

-코드

#include <stdio.h>
 
#define SIZE 100
 
#define SWAP(a, b, type) do { \
    type tmp;    \
    tmp = a;    \
    a    = b;    \
    b    = tmp;    \
}while (0)
 
void bubbleSort(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 버블 정렬을 수행하는 함수 
    int i;
    int j;
 
    for (i = 0; i < N; i++) {
        for (j = 1; j < N-i; j++) {
            if (ary[j-1] > ary[j]) {
                SWAP(ary[j-1], ary[j], int);
            }
        }
    }
}
void printAry(int ary[], int N) {
    // 배열의 자료형(ary)과 배열의 크기(N)를 
    // 입력받고 배열의 원소를 출력하는 함수 
    int i;
 
    for (i = 0; i < N; i++) {
        printf("%d ", ary[i]);
    }
    printf("\n");
}
int main(void) {
    int ary[SIZE];
    int i;
    int N;
 
    // 배열의 크기를 표준입력으로부터 입력
    scanf("%d", &N);
 
    // 배열의 크기 만큼 반복문을 통해 배열의 원소를 초기화
    for (i = 0; i < N; i++) {
        scanf("%d", &ary[i]);
    }
 
    // 버블 정렬 함수를 호출하고 배열의 원소를 출력
    bubbleSort(ary, N);
    printAry(ary, N);
    //fflush(stdout);
    getchar();
    getchar();
 
    return 0;
}