BubbleSort

둘째는 BubbleSort, 버블 정렬이다.

원리

1. 0부터 끝요소까지 반복한다.( current < N )

2. 현재요소( current )와 다음 요소 ( current + 1 )를 비교하여 다음 요소가 더 작으면 교환이 일어난다.

3. 가장 뒤부터 정렬이 일어난다.

특징

1. 많은 횟수를 비교, 교환 하기 때문에 속도가 느리다.

2. pass. 1에서 교환이 일어나지 않을 경우 이미 정렬되어 있는 배열이지만 이것을 확인하지 못하고 정렬을 계속 시도한다. 

연산시간

1. 처음에는 N-1번 비교하여 가장 큰 수를 맨뒤로 밀어낸다.

2. 그렇게 [ (N - 2) + (N - 3) + (N - 4) + ... + 1 ] 만큼 비교 및 교환을 수행한다.

3. 식으로 나타내면   = n(n-1) / 2 이며 O표기법으로는 O(n^2)이 된다.

코드

//BUBBLESORT
 
void BubbleSort(int* array, int size)
{
    for(int i = 0 ;i < size ;i++)     // i == (0 ~ size)
    {
        for(int j = 0 ;j < (size - 1) - i ;j++ ){ // j == (0 ~ (size - 1) - i)
            if(array[j] > array[j+1]) // (j) > (j + 1) 이면 교환
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
int const MAX = 5;                    // Max 값
int g_arr[MAX] = { 0, };              // 배열 초기화
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);    // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);   // 역순 배열 생성
    RandomNumber(g_arr, MAX);         // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);          // 배열 출력
    printf("\n");
    clock_t start = clock();          // 시작 시간
    BubbleSort(g_arr, MAX);           // BubbleSort
    clock_t end = clock();            // 끝 시간
 
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);        // 배열 출력
    printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}

결과

시간

시간은 MAX 값 100,000 을 기준으로 측정하였다.

랜덤 배열 : 33.80
역순 배열 : 22.30
순열 배열 : 17.60

결론

버블정렬은 구현하기가 가장 쉬웠던 것 같다.

하지만 이미 정렬된 배열에 대해서 알지 못하고 모두 비교해보기 때문에 적절한 대처방안이 필요할 것 같다. 대처 방안은 언젠가 추가할 것이다.

역시 O(n^2)의 알고리즘 답게 요소가 많아질 수록 응답 시간이 길어졌다.