버블 정렬 (코드업 1441: 버블 정렬)

버블 정렬 알고리즘은 매우 비효율적이며 시간이 오래 걸리는 알고리즘이지만, 이해하기 쉽고 직관적이어서 첫 번째로 가져왔습니다.

버블 정렬을 헝가리 무용으로 표현한 영상입니다.

오름차순으로 정렬하려는 상황을 생각하겠습니다.

1번째와 2번째 원소를 먼저 비교합니다. 2번째 원소가 1번째 원소보다 더 크면 서로를 바꿉니다.
2번째와 3번째, ... n-1번째와 n번째까지 계속 이것을 수행합니다. 이 과정을 시행 1회라고 부르겠습니다.

그리고 위 시행을 n번 반복하면 됩니다.
하지만, 횟수를 더 줄이려면, 1번째 시행에서는 n번째까지, 2번째 시행에서는 n-1번째까지, ... , n-1번째 시행에서는 2번째까지만 탐색(크기 비교 및 교체)해도 됩니다.

왜냐하면, 버블 정렬은 앞에서부터 차례대로 연속된 두 원소를 훑으면서 둘 중에 더 큰 값을 뒤쪽으로 계속 떠넘기기 때문에, 1회의 시행이 끝나면 시행한 구간에서 최댓값은 가장 뒤쪽에 있는 것이 보장되기 때문입니다. 예를 들어 설명하자면,

4 3 1 2

위 데이터에 시행을 한 번 거치면

4 3 1 2 → 3 4 1 2 → 3 1 4 2 → 3 1 2 4

위와 같이 위치가 바뀝니다. 화살표 한 번이 탐색(크기 비교 및 교체) 한 번이니, 세 번의 탐색이 있었습니다.
아직 정렬이 완료되진 않았지만, 데이터에서 가장 큰 값이었던 4는 가장 뒤로 갔습니다. 따라서 다음 시행은 1번째와 2번째 원소 탐색, 2번째와 3번째 원소 탐색만 하면 됩니다. 3번째와 4번째는 이미 4번째가 더 큼을 알고 있으니까요.

그럼 버블 정렬을 마저 계속해보겠습니다.


두 번째 시행에서는 두 번의 탐색을 합니다.

1 3 2 4 → 1 2 3 4 → 1 2 3 4

이미 정렬이 끝났는데도 계속 탐색을 하고 있음을 알 수 있습니다.

세 번째 시행에서는 한 번의 탐색을 합니다.

1 2 3 4 → 1 2 3 4

역시나 데이터는 이미 정렬되었는데 버블 정렬 알고리즘이 끝나지 않습니다.

이를 해결하려면, 시행이 한 번 이루어질 때마다 정렬이 완료하였는지 검사하는 코드가 필요합니다. (탐색 한 번마다 검사하는 것은 오히려 시간이 오래 걸립니다.) 이 코드는 생략하겠습니다. (배열 전체를 앞쪽에서부터 훑으면서 i번째 원소보다 i+1번째 원소가 더 작은 상황이 있는지 확인하면 됩니다. 그렇다면 아직 내림차순인 구간이 있다는 것이니까요.)


그럼 버블 정렬을 C 코드로 만들어보겠습니다.

#include <stdio.h>

int a[10001];
int n, i, j, temp;

int main() {
    scanf("%d", &n);
    for (i=1; i<=n; i++)
        scanf("%d", &a[i]);

    for (i=1; i<n; i++) {
        for (j=1; j<n; j++) {
            if (a[j] > a[j+1]) {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }

    for (i=1; i<=n; i++)
        printf("%d\n", a[i]);
    return 0;
}

코드업의 1441번 문제, 버블 정렬입니다. 원 문제에서는 빈 칸만 작성하게 되어있으므로, for(j=1; ~ 부분만이 답입니다.

모쪼록 이 코드를 해설해보겠습니다. a[1]부터 a[n]까지 데이터가 담겨 있습니다. 여기서 버블 정렬 코드는 이중 for문 부분입니다. i를 반복하는 for문이 시행의 반복이고, j를 반복하는 for문이 탐색의 반복입니다.

temp는 무슨 역할일까요? 비유적으로 두 병에 들어있는 주스를 서로 바꾼다고 생각해봅시다. 그러면 빈 병이 필요합니다. 오렌지 주스 병에 든 오렌지 주스를 빈 병에 옮겨담고, 포도 주스 병에 든 포도 주스를 오렌지 주스 병에 옮겨담고, 빈 병에 든 오렌지 주스를 포도 주스 병에 옮겨담습니다. 그러면 최종적으로 두 병의 내용물이 바뀌죠. 여기서 temp는 빈 병의 역할입니다. 배열의 두 원소를 바꾸기 위해 잠시 값을 옮겨둘 빈 공간이죠.

앞서 언급했듯, 탐색은 항상 n번 할 필요는 없습니다.
1번째 시행에서는 n번째까지,
2번째 시행에서는 n-1번째까지,
...
i번째 시행에서는 n-i+1번째까지 탐색해도 됩니다. 따라서 아래 코드는

for (j=1; j<n; j++) {

다음처럼 바꾸면 더 빠른 속도로 정렬할 수 있습니다.

for (j=1; j<n-i; j++) {

선택 정렬이나 삽입 정렬은 실제 쓰일 일이 거의 없으므로 우선은 다루지 않겠습니다. (버블 정렬도 실제로는 잘 안 쓰지만, 정렬의 소개차 가져왔습니다.) 이것의 설명을 원하시거나 질문이 있으시다면 댓글 부탁드립니다.