버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

---

#include <stdio.h>
int main()
{
    int arr[] = { 10,30,55,27,19 };
    int i, j;
 
    printf("정렬 전\n");
    for (i = 0; i < 5; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    for (i = 5 - 1; i > 0; i--)
    {
        for (j = 0; j < i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        printf("%d, %d, %d, %d, %d\n", 
            arr[0], arr[1], arr[2], arr[3], arr[4]);
    }
    printf("\n");
 
    return 0;
}

< 출력 >

정렬 전

10 30 55 27 19

10, 30, 27, 19, 55

10, 27, 19, 30, 55

10, 19, 27, 30, 55

10, 19, 27, 30, 55

맨 뒤에서부터 정렬이 되어가고 있는 것을 볼 수가 있다.

이해가 안 간다면 버블 정렬 여기를 들어가서 그림으로 보도록 한다.

소스 분석을 하자면 12번째 줄에 i=5-1가 되어있다. 그 이유는

정렬 전
10 30 55 27 19
10 30 27 19 -858993460
10 27 19 -858993460 30
10 19 -858993460 27 30
10 -858993460 19 27 30
-858993460 10 19 27 30

-1을 안 해주면 이렇게 쓰레기 값이 출력이 된다.

내림차순으로 설정을 해주려면 16째 줄에 부등호를 반대쪽으로 바꿔주면 된다.

버블 정렬은 정렬하는 기법 중에 하나인데 시간 복잡도로 따지면 O(n^2)가 된다.

반복문이 2개 돌아가니 n^2이다.

이 버블 정렬의 단점은 정렬이 되어 있는 데이터가 있어도 계속 반복문이 돌아가게 된다.

그래서 우리에겐 향상된 버블 정렬이 있다.

---

#include <stdio.h>
#include <stdbool.h> //bool 자료형 사용하기 위해.
int main()
{
    int arr[5] = { 3,4,5,6,7 };
    bool flag = true;
 
    for (int i = 5 - 1; i>0 && flag; i--) {
        for (int j = 0; j<i; j++) {
            flag = false;
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true; //한 회전에 교환이 있다면 true.
            }
        }
        printf("%d, %d, %d, %d, %d\n",
            arr[0], arr[1], arr[2], arr[3], arr[4]);
    }
    return 0;
}

< 출력 >

3, 4, 5, 6, 7

향상된 버블 정렬 알고리즘은 정렬이 되어 있다면 반복문을 끝까지 안 돌고 끝내게 된다.

향상된 버블 정렬을 시간 복잡도로 나타내면 최악의 경우는 O(n^2)이고

최선의 경우는 O(n)이다. 버블 정렬보다는 향상된 버블 정렬을 쓰는 게 더 낫다.

정리를 하자면 버블 정렬은 비효율적이고 향상된 버블 정렬은 효율적이다.

2018/07/18 - [프로그래밍/C] - qsort(퀵 정렬) 정렬하기