28. Bubble Sort

버블 정렬(거품 정렬, Bubble Sort)은 가장 간단한 정렬 방법의 하나로 인접한 두 원소를 비교하는 과정을 반복한다. 처음에는 $1$번째와 $2$번째 원소를 비교하고, $2$번째와 $3$번째 원소를 비교하고, 이런 식으로 계속해서 비교하며 $(n-1)$번째와 $n$번째 원소를 비교한다. 만약 비교한 두 원소의 순서가 바뀌어 있다면 두 원소를 바꾼다. 이렇게 차례대로 한 번 비교를 실행하면 $n$번째 원소를 제자리에 넣을 수 있다. 이제 정렬해야 하는 원소는 $(n-1)$개이고, 다시 앞에서부터 비교를 실행하는데 이번에는 $(n-2)$번째와 $(n-1)$번째 원소를 비교하는 것까지 하면 된다. 이런 식으로 차례대로 한 번 비교를 실행할 때마다 원소 하나의 위치가 추가로 맞게 되고 이 과정을 $(n-1)$번 반복하면 $n$개의 원소를 정렬할 수 있다. ($n$번이 아닌 이유는 두 번째 원소까지의 위치가 모두 맞았다면 첫 번째 원소의 위치 역시 맞게 되기 때문이다.)

 

$n$개의 원소로 이루어진 정수 배열 $a$를 오름차순으로 정렬하는 코드를 통해 작동 방식을 더 자세히 이해할 수 있다. 인덱스는 1-based이다.

 

C++의 구현은 다음과 같다. (swap 함수는 헤더파일 <bits/move.h>에 정의되어 있다. <algorithm> 헤더를 인클루드해도 사용할 수 있다.)

for(k = 1; k <= n - 1; k++)
{
    for(i = 1; i <= n - k + 1; i++)
    {
        if(a[i] > a[i + 1])swap(a[i], a[i+1]);
    }
}

C에는 swap 함수가 없어서 이런 식으로 구현해야 한다.

for(k = 1; k <= n - 1; k++)
{
    for(i = 1; i <= n - k + 1; i++)
    {
        if(a[i] > a[i + 1])
        {
            int t = a[i];
            a[i] = a[i + 1];
            a[i + 1] = t;
        }
    }
}

또한 반복문을 다음과 같이 수정할 수도 있다.

------------------------------------------------------------

for(k = n - 1; k > 0; k--)
{
    for(i = 1; i <= k; i++)
    {
        if(a[i] > a[i + 1])swap(a[i], a[i+1]);
    }
}

------------------------------------------------------------

for(k = n; --k;)
{
    for(i = 0; i++ < k;)
    {
        if(a[i] > a[i + 1])swap(a[i], a[i+1]);
    }
}

------------------------------------------------------------

정렬할 원소가 정수나 실수 자료형이라면 이런 방법으로 두 원소를 바꿀 수도 있다.

x += y;
y = x;
x -= y;

정수 자료형의 경우 이런 방법도 가능하다.

x ^= y ^= x ^= y;

다음은 버블 정렬 과정을 시뮬레이션한 것이다.

어떤 방법으로 두 원소를 맞바꾸던간에, 비교 횟수의 총합이 $n(n-1)/2$가 되어 $\Theta(n^2)$의 시간복잡도를 가짐을 확인할 수 있다. 이 시간복잡도 때문에 $n$이 $10^4$를 넘어가면 속도가 느려지게 되고, 이보다 많은 원소를 정렬할 때는 더 빠른 정렬을 사용해야 한다.

 

[연습문제]

 

BOJ 2750. 수 정렬하기 (Bronze I)

버블 정렬 기본 문제이다.

 

→ solved.ac tag: sorting