버블정렬(Bubble Sort)이란?

 

개념

버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.

 

 

 

과정

버블 정렬

(굵은 글자는 인접한 두 개의 비교를 뜻하고, 빨간색은 자리 교환이 이루어진 것)

 

{16, 2, 31, 14, 5} 리스트가 있을 때 버블 정렬을 시작하면

1회전

{2, 16, 31, 14, 5} ⇒ (16, 2) 비교하여 16이 더 크므로 자리 교환  

{2, 16, 31, 14, 5} ⇒ (16, 31) 비교하여 31이 더 크므로 자리 교환 안함

{2, 16, 14, 31, 5} ⇒ (31, 14) 비교하여 31이 더 크므로 자리 교환

{2, 16, 14, 5, 31} ⇒ (31, 5) 비교하여 31이 더 크므로 자리 교환  

1회전을 끝내면 가장 큰 자료인 31이 맨 뒤로 이동하게 된다.

2회전

1회전 때 나온 맨 뒷자리를 제외한 원소들로 반복하게 된다.

{2, 16, 14, 5, 31} ⇒ (2, 16) 비교 후 자리 교환 안함

{2, 14, 16, 5, 31} ⇒ (16, 14) 비교 후 자리 교환

{2, 14, 5, 16, 31} ⇒ (16, 5) 비교 후 자리 교환

2회전을 끝내면 31을 제외하고 가장 큰 자료인 16이 맨 뒤로 가게 된다.

3회전

{2, 14, 5, 16, 31} ⇒ (2, 14) 비교 후 자리 교환 안함

{2, 5, 14, 16, 31} ⇒ (14, 5) 비교 후 자리 교환 

2회전에서 가장 큰 값인 16을 제외하고 가장 큰 자료인 14가 맨 뒤로 가게 된다.

4회전

{2, 5, 14, 16, 31} ⇒ (2, 5) 비교 후 자리 교환 안함 

정렬이 끝남

 

 

 

구현(C++)

#include <stdio.h>
int main()
{
    int n, i, j, a[5], temp;
    scanf("%d", &n);        // 데이터의 개수 n을 정한다.
    for (i = 0; i < n; i++) // n개만큼 데이터 값을 받는다.
    {
        scanf("%d", &a[i]);
    }
    // 버블 정렬 시작
    for (i = 0; i < n - 1; i++) // 마지막 값은 자동 정렬되므로 n-1번까지만 반복한다.
    {
        for (j = 0; j < n - i - 1; j++) // i번 돌때마다 마지막 값에는 큰 값이 들어오므로 끝까지 비교할 필요가 없다. 따라서 n-i-1번까지만 비교한다.
        {
            if (a[j] > a[j + 1]) // 인접한 2개를 비교했을 때 처음 위치값이 크다면 자리 교환
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    // 버블 정렬 끝났으므로 출력한다.
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

이렇게 버블 정렬이 동작하게 된다.

버블 정렬을 돌리면서 생각났는데 정렬이 이미 끝났어도 현재 코드에서는 계속 반복하여 비교하게 된다.

만약 위 그림처럼 {1, 2, 3, 4, 5}가 들어와서 버블 정렬을 시작하면 1회전에서 저렇게 의미없이 비교를 하게된다.

그리고 이 과정을 4회전까지 하게 된다.

따라서 정렬이 끝났는데도 계속 반복하는 것을 중단시키려면 다음 코드에서 check를 추가해보자.

#include <stdio.h>
int main()
{
    int n, i, j, a[5], temp, check;
    scanf("%d", &n);        // 데이터의 개수 n을 정한다.
    for (i = 0; i < n; i++) // n개만큼 데이터 값을 받는다.
    {
        scanf("%d", &a[i]);
    }
    // 버블 정렬 시작
    for (i = 0; i < n - 1; i++) // 마지막 값은 자동 정렬되므로 n-1번까지만 반복한다.
    {
        check = 0; // 1번 돌 때마다 0으로 초기화한다.
        for (j = 0; j < n - i - 1; j++) // i번 돌때마다 마지막 값에는 큰 값이 들어오므로 끝까지 비교할 필요가 없다. 따라서 n-i-1번까지만 비교한다.
        {
            if (a[j] > a[j + 1]) // 인접한 2개를 비교했을 때 처음 위치값이 크다면 자리 교환
            {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
        if (check == 0) // 모든 자리의 값을 비교했는데 자리 교환이 이루어지지 않았다면 이미 정렬이 끝난 상태이므로 반복을 그만한다.
            break;
    }
    // 버블 정렬 끝났으므로 출력한다.
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

위 코드처럼 1회전 할 때마다 check를 0으로 초기화해주고, 내부 for문일 때 전부 비교를 하는데 자리교환이 이루어지지 않으면 정렬이 끝났다고 판단되어 반복을 끝내게 된다.

 

 

 

시간 복잡도

최악일 때는 이것 또한 선택 정렬(Selection Sort)이랑 똑같은 시간 복잡도인 O(n^2)이다.

하지만 중간에 필요없는 반복을 끝내는 최선(최적)일 때를 보면 1번만에 끝나기도 하므로 이 때는 O(n)이 된다.

 

 

 

정렬 비교

교환 작업이 많이 이루어져서 이것 보다는 선택 정렬을 사용하는 것이 성능적으로 더 우수하다.