버블정렬 (Bubble Sorting)

버블 정렬은 오름차순 기준으로, 인접한 2개의 레코드를 비교하여 정렬되어 있지 않다면 서로 교환하는 비교-교환 과정을 처음부터 끝까지 비교한다. 한 회전에서 2개의 레코드를 계속 비교하기 때문에 각 회전마다 그 리스트의 가장 큰 숫자는 항상 제자리(맨 뒤쪽)로 찾아간다.

1. 리스트의 첫 번째, 두 번째 숫자를 선택

2. 이 둘을 비교, 순서가 맞지 않으면 서로 교환

3. 1회전이 끝나면 가장 큰 숫자는 뒤로 가게 된다.

4. 위 과정을 정렬이 안된 리스트에서 반복

예를 들어 요소의 갯수가 5개이고

3 2 6 1 5  라는 배열이 있다면

1회전 - 2 3 6 1 5

2회전 - 2 3 6 1 5

3회전 - 2 3 1 6 5

4회전 - 2 3 1 5 6

위와 같은 절차가 1번의 스캔이다.

다른 정렬은 1번의 스캔을 예로 들었지만, 버블 정렬의 경우는 1번의 회전을 예로 들었다.

만약 스캔을 기준으로 한다면 다음과 같은 과정이다.

3 2 6 1 5

1스캔 - 2 3 1 5 6

2스캔 - 2 1 3 5 6

3스캔 - 1 2 3 5 6

4스캔 - 1 2 3 5 6

버블 정렬은 간단하다.

하나의 스캔은 j=0부터 j=i-1까지 반복하는 루프로 구성되고, j번째 요소와 j+1번째 요소를 비교하여 크기순이 아니면 교환한다.

i는 하나의 스캔이 끝날 때 마다 1씩 감소한다. 이런 스캔 과정이 n-1번 반복한다.

버블정렬의 코드는 다음과 같다.

void bubble_sort(int list[], int n) {
    int tmp;

    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < i; j++)
        if (list[j] > list[j + 1]) // 앞뒤의 레코드를 비교한 후 교체
            SWAP(list[j], list[j + 1], tmp);
    
        printf("%d회 정렬 결과 : ", i);
        for (int k = 0; k < n; k++)
            printf("%d ", list[k]);
        printf("\n");
    }
}

전체 프로그램

정렬하기 전의 배열 상태와 각 회전수에 정렬된 배열 상태를 출력한다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 10
#define SWAP(x, y, t) (t=x, x=y, y=t)

void bubble_sort(int list[], int n) {
    int tmp;

    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < i; j++)
            if (list[j] > list[j + 1]) // 앞뒤의 레코드를 비교한 후 교체
        SWAP(list[j], list[j + 1], tmp);

        printf("%d회 정렬 결과 : ", i);
        for (int k = 0; k < n; k++)
            printf("%d ", list[k]);
        printf("\n");
    }
}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;

    printf("<버블정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < n; i++) {
        list[i] = rand() % n;
        printf("%d ", list[i]);
    }
    printf("\n");

    bubble_sort(list, n); // 버블 정렬 호출

    printf("최종 정렬 결과 : ");
    for (int i = 0; i < n; i++)
        printf("%d ", list[i]);
    printf("\n");
    system("pause");
}

 

각 스캔과정은 생략한다.

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>

#define MAX_SIZE 40000
#define SWAP(x, y, t) (t=x, x=y, y=t)

void bubble_sort(int list[], int n) {
    int tmp;

    clock_t start = clock(); // 시간재기 시작
    for (int i = n-1; i > 0; i--) {
        for (int j = 0; j < i; j++)
            if (list[j] > list[j + 1])
        SWAP(list[j], list[j + 1], tmp);
    }
    clock_t end = clock(); // 시간재기 끝

    double diff = (double)(end - start) / 1000;
    printf("버블정렬\n크기 : 40000개\n%.4lf초", diff);

}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;

    for (int i = 0; i < n; i++) {
        list[i] = rand() % n;
    }

    bubble_sort(list, n); // 버블 정렬 호출

    printf("\n");
    system("pause");
}

버블 정렬의 비교 횟수는 최상, 평균, 최악 어떠한 경우에도 항상 일정하고 다음과 같다.

 

 

이동 횟수는 입력 자료가 역순으로 정렬되어 있는 경우 발생하고, 비교 연산의 횟수에 3을 곱한 값이다.

왜냐하면 하나의 SWAP함수가 3개의 이동을 포함하고 있기 때문이다.

최상의 경우는 입력 자료가 이미 정렬이 되어 있는 경우이기 때문에 자료 이동이 한번도 발생하지 않는다.

평균적인 경우에는 자료이동이 0번에서 i번까지 같은 확률로 일어날 것이다.

 

따라서 이를 기반으로 계산해보면 의 복잡도를 가지는 알고리즘이다.

 

버블 정렬의 가장 큰 문제점은 순서에 맞지 않은 요소를 인접한 요소와 교환한다는 것이다.

하나의 요소가 가장 왼쪽에서 가장 오른족으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

특히 특정 요소가 최종 정렬 위치에 이미 있더라도 교환된다. 일반적으로 자료의 교환(swap)작업이 자료의 이동(move)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.