컴공 일기113

신촌 연합 알고리즘 캠프 첫 번째 수업에서 다룬 여러 정렬 중, 가장 기본적인 버블 정렬 구현 예제입니다. 이 예제에서는, 실행 결과를 보면 알 수 있는데 오름차순으로 정렬을 해봤습니다. 방향만 바꾸면 내림차순 정렬 또한 버블 정렬로 구현할 수 있죠. 하여튼 버블 정렬은 시간복잡도를 꽤 잡아먹기 때문에, 좋은 알고리즘은 아닙니다. (물론, 다른 정렬에 비해서 구조가 간단하기 때문에, 실행 중 오류가 날 가능성이 현저히 떨어진다는 측면에선 좋게 봐줄만도 하지요..) 

하지만, 어떤 한 과목을 100점 맞은 사람은 0점을 맞을 수도 있는 법이지요. 비효율적인 이유를 알아야, 효율적인 코드를 잘 작성할 수 있을 겁니다.

약간의 개선을 통해 버블 정렬의 연산량을 줄여보긴 했지만, 퀵 정렬에 비하면 여전히 안타깝기 그지없는 코드입니다. 

#include <stdio.h>

void BubbleSort(int DataSet[], int Length)

{

    int i = 0;

    int j = 0;

    int temp = 0;

    for (i = 0; i < Length - 1; i++)

    {    

        int excg = 0;

        for (j = 0; j < Length - (i + 1); j++)

        {

            if (DataSet[j] > DataSet[j + 1])

            {

                temp = DataSet[j + 1];

                DataSet[j + 1] = DataSet[j];

                DataSet[j] = temp;

                excg++;

            }

        }

        if (excg == 0)

        {

            printf("개선된 버블 정렬이 작동하고 있습니다!\n");

            break;

        }

    }

}

int main()

{

    int DataSet[] = { 6,4,3,2,1,5 };

    int Length = sizeof(DataSet) / sizeof(DataSet[0]);

    int i = 0;

    BubbleSort(DataSet, Length);

    for (i = 0; i < Length; i++)

    {

        printf("%d ", DataSet[i]);

    }

    return 0;

}

[실행결과]

개선된 버블 정렬이 작동하고 있습니다!

1 2 3 4 5 6