버블 정렬 (Bubble Sort)

들어가는 말

버블 정렬은 인접한 두 값을 비교해 정렬 기준에 맞지 않으면 교환하는 방식으로 배열을 정렬한다.
한 회차가 끝날 때마다 오름차순에서는 최댓값이, 내림차순에서는 최솟값이 오른쪽부터 차례대로 확정된다.
인접한 값이 반복해서 교환되며 이동하는 모습이 거품이 떠오르는 모습과 비슷해서 버블 정렬이라고 부른다.
시간 복잡도가 O(n²)라 효율적인 알고리즘은 아니지만, 구현이 단순해서 정렬의 기본 구조를 이해하기 좋다.

정렬 과정 살펴보기

7 2 6 1 4를 오름차순으로 정렬해 보자.

1회차

처음에는 배열 전체가 아직 정렬되지 않은 구간이다.
원소가 n개인 배열에서는 왼쪽부터 인접한 두 값을 n - 1번 비교하고, 왼쪽 값이 더 크면 교환한다.

단계	비교	판단	배열 상태
1회차 시작 전	-	-	7 2 6 1 4
1회차 1번째	7과 2	7이 더 크므로 교환	2 7 6 1 4
1회차 2번째	7과 6	7이 더 크므로 교환	2 6 7 1 4
1회차 3번째	7과 1	7이 더 크므로 교환	2 6 1 7 4
1회차 4번째	7과 4	7이 더 크므로 교환	2 6 1 4 7

이 과정을 마치면 가장 큰 값이 오른쪽 끝으로 이동해 자리가 확정된다.

2회차

7의 자리는 이미 확정되었으므로 2 6 1 4만 비교한다.

단계	비교	판단	배열 상태
2회차 시작 전	-	-	2 6 1 4 7
2회차 1번째	2와 6	순서가 맞으므로 유지	2 6 1 4 7
2회차 2번째	6과 1	6이 더 크므로 교환	2 1 6 4 7
2회차 3번째	6과 4	6이 더 크므로 교환	2 1 4 6 7

2회차가 끝나면 6의 자리가 확정된다.

3회차

6과 7의 자리는 이미 확정되었으므로 2 1 4만 비교한다.

단계	비교	판단	배열 상태
3회차 시작 전	-	-	2 1 4 6 7
3회차 1번째	2와 1	2가 더 크므로 교환	1 2 4 6 7
3회차 2번째	2와 4	순서가 맞으므로 유지	1 2 4 6 7

3회차가 끝나면 4의 자리가 확정된다.

4회차

4, 6, 7의 자리는 이미 확정되었으므로 1 2만 비교한다.

단계	비교	판단	배열 상태
4회차 시작 전	-	-	1 2 4 6 7
4회차 1번째	1과 2	순서가 맞으므로 유지	1 2 4 6 7

4회차가 끝나면 2의 자리가 확정된다.
원소 5개 중 4개의 자리가 확정되면 남은 값의 자리도 자연스럽게 정해지므로 정렬이 끝난다.

회차별 정렬 과정 요약

회차	비교 횟수	교환 횟수	확정되는 값	배열 상태
시작 전	-	-	-	7 2 6 1 4
1회차	4번	4번	7	2 6 1 4 7
2회차	3번	2번	6	2 1 4 6 7
3회차	2번	1번	4	1 2 4 6 7
4회차	1번	0번	2	1 2 4 6 7

시간 복잡도

버블 정렬은 각 회차마다 미정렬 구간의 처음부터 끝까지 이동하며 인접한 두 원소를 모두 비교한다.
배열에 원소가 n개 있다면 1회차에서는 n - 1번, 2회차에서는 n - 2번 비교하며 회차가 진행될수록 비교 횟수가 한 번씩 줄어든다.
따라서 총 비교 횟수는 다음과 같다.

$$(n - 1) + (n - 2) + \cdots + 2 + 1 = \frac{n(n - 1)}{2} = \frac{n^2 - n}{2}$$

예를 들어 원소가 5개라면 4 + 3 + 2 + 1 = 10번 비교한다.

이 비교 횟수는 배열의 정렬 상태와 무관하다.
이미 정렬된 배열이라도 매 회차 미정렬 구간의 모든 인접 원소 쌍을 끝까지 비교하기 때문이다.
그러므로 최선, 평균, 최악의 경우 모두 시간 복잡도는 O(n²)이다.

비교와 달리 두 원소의 교환 횟수는 배열의 정렬 상태에 따라 달라진다.
이미 오름차순으로 정렬된 배열에서는 교환이 일어나지 않지만, 내림차순으로 정렬된 배열에서는 비교할 때마다 교환이 일어나 총 n(n - 1) / 2번 교환한다.
그러나 교환 횟수와 관계없이 전체 비교 횟수는 변하지 않으므로 시간 복잡도에는 영향을 주지 않는다.

소스 코드

#include <stdio.h>

int main(void)
{
    int arr[] = { 7, 2, 6, 1, 4 };
    int size = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]); // Result: 1 2 4 6 7
    }

    return 0;
}

구현 설명

바깥 반복문의 i는 0부터 시작하는 회차 인덱스로, 지금까지 자리가 확정된 원소의 수와 같다.
원소 size개 중 size - 1개의 자리만 확정하면 되므로 바깥 반복문은 size - 1번 실행한다.

안쪽 반복문의 j는 현재 비교할 왼쪽 원소의 인덱스다.
안쪽 반복문의 조건식 j < size - 1 - i가 어떻게 정해지는지 살펴보자.

첫 회차에서는 가장 큰 원소의 자리를 확정하기 위해 인접한 두 원소를 size - 1번 비교한다.
한 회차가 끝날 때마다 현재 비교 구간에서 가장 큰 원소의 자리가 확정되므로 다음 회차의 비교 대상에서 제외해야 한다.
이를 위해 회차를 나타내는 i만큼 안쪽 반복문의 비교 범위를 줄여야 한다.
따라서 안쪽 반복문의 조건식은 j < size - 1 - i가 된다.