[C언어 알고리즘] 정렬(4) - 거품정렬(Bubble sort)

이번 시간은 거품정렬(Bubble sort)입니다. 거품정렬은 인접요소(Adjacent element)를 비교하여 교환하는 모습이 마치 거품이 보글보글 하는 모양이라서 붙은 이름입니다. 

 

거품정렬의 의사코드(Pseudo code)는 다음과 같습니다.

 

거품정렬 알고리즘

1. i=0
2. i가 n-1이면 끝낸다
  2.1 j=1
    2.1.1 j가 n-i가 되면 2.2로 간다.
    2.1.2 a[j-1] > a[j]이면 두 값을 교환
    2.1.3. j를 하나 증가 시키고 2.1로 돌아간다.
  2.2. i를 하나 증가 시기코 2로 돌아간다.

j가 n-i까지 반복하는 이유는 n-i이후는 이미 가장 큰 값들로 정렬이 되어 있는 상태이기 때문입니다. 

 

첫 번째 수행은 다음과 같습니다. 첫 번째 수행에서 값을 교환하여 배열의 가장 마지막 요소에 가장 큰 값을 옮기는 수행을 하므로 이 부분만 이해하면 거품 정렬의 대부분을 이해할 수 있습니다.

거품정렬 첫번 째 수행

내용을 보면 배열의 첫번 째 요소의 값을 기준 값으로 삼고, 다음 요소가 기준 값보다 작으면 교환을 하는 과정을 반복하고 기준 값보다 작지 않으면 기준값을 다음 요소로 배열의 끝까지 비교와 교환을 계속 진행한다. 결과적으로 배열의 마지막 요소가 't'로 가장 큰 값이 정렬 되었음을 알 수 있습니다.

두 번째 수행의 경우엔 't'를 제외한 나머지 요소 중 가장 큰 값인 'r'이 't' 앞에 놓여질 것입니다.

 

아래는 C언어로 작성한 소스입니다.

#include <stdio.h>
#include <string.h>

void print_data(char a[], int n);

void bubble_sort(char a[], int n)
{
    int i, j;
    char t;
    for (i = 0; i< n; i++) {
        for(j = 1; j < n-i; j++) {
            if (a[j-1] > a[j]) {
                t = a[j-1];
                a[j-1] = a[j];
                a[j] = t;
                printf ("%d step>>>", i+1);
                print_data(a,n);
            }
        }
        print_data(a, n);
    }
}

void print_data(char a[], int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf ("%c ", a[i]);
    }
    printf ("\n");
}

void main (int argc, char *argv[])
{
    char data[] = "learnalgorithm";
    print_data(data, strlen(data));
    bubble_sort(data, strlen(data));
}

실행 결과는 다음과 같습니다.

PS C:\CS> .\bubble_sort.exe
l e a r n a l g o r i t h m 
1 step>>>e l a r n a l g o r i t h m
1 step>>>e a l r n a l g o r i t h m
1 step>>>e a l n r a l g o r i t h m
1 step>>>e a l n a r l g o r i t h m 
1 step>>>e a l n a l r g o r i t h m 
1 step>>>e a l n a l g r o r i t h m
1 step>>>e a l n a l g o r r i t h m
1 step>>>e a l n a l g o r i r t h m 
1 step>>>e a l n a l g o r i r h t m
1 step>>>e a l n a l g o r i r h m t
e a l n a l g o r i r h m t
2 step>>>a e l n a l g o r i r h m t 
2 step>>>a e l a n l g o r i r h m t
2 step>>>a e l a l n g o r i r h m t
2 step>>>a e l a l g n o r i r h m t
2 step>>>a e l a l g n o i r r h m t 
2 step>>>a e l a l g n o i r h r m t
2 step>>>a e l a l g n o i r h m r t 
a e l a l g n o i r h m r t
3 step>>>a e a l l g n o i r h m r t
3 step>>>a e a l g l n o i r h m r t
3 step>>>a e a l g l n i o r h m r t 
3 step>>>a e a l g l n i o h r m r t
3 step>>>a e a l g l n i o h m r r t
a e a l g l n i o h m r r t
4 step>>>a a e l g l n i o h m r r t 
4 step>>>a a e g l l n i o h m r r t
4 step>>>a a e g l l i n o h m r r t
4 step>>>a a e g l l i n h o m r r t
4 step>>>a a e g l l i n h m o r r t
a a e g l l i n h m o r r t 
5 step>>>a a e g l i l n h m o r r t
5 step>>>a a e g l i l h n m o r r t
5 step>>>a a e g l i l h m n o r r t
a a e g l i l h m n o r r t 
6 step>>>a a e g i l l h m n o r r t
6 step>>>a a e g i l h l m n o r r t
a a e g i l h l m n o r r t
7 step>>>a a e g i h l l m n o r r t
a a e g i h l l m n o r r t
8 step>>>a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t
a a e g h i l l m n o r r t

실행결과는 각 step별로 배열의 요소의 교환이 일어날 때마다 로그를 찍어봤습니다.

첫 번째 step에서 교환이 가장 많이 이뤄졌고, 8번째 이후로는 교환없이 진행되었습니다. 거품정렬은 자료가 정렬이 되어 있는 경우 비교만 하고 교환이 없기 때문입니다.

요즘도 학교에서 거품정렬에 대해 기본으로 가르치고 있는지 모르겠지만, 거품정렬은 우리가 다룰 정렬 알고리즘 중에서 가장 느리고 무식한 녀석입니다. 그냥 이런 정렬 알고리즘도 있구나 선에서 넘어가시면 되겠습니다.

지금까지 거품 정렬이었습니다.