1. 버블 정렬(Bubble Sort)

Goal

---

• Bubble Sort란?
• Bubble Sort 구현
• Bubble Sort 시간복잡도, 공간복잡도 계산

 

Bubble Sort란?

---

서로 인접한 원소의 대소를 비교하고, 조건에 맞게 자리를 교환하며 정렬하는 알고리즘. 대략적인 과정은 아래를 따른다.

1. 1번째 원소와 2번째 원소를 비교하고 정렬하고, 2번째와 3번째, ... n-1번째와 n번째를 정렬한다.
2. 1회차가 끝나면, 처음부터 다시 시작하여 n-2번째와 n-1번째를 정렬할 때 까지 진행한다.
3. 위 과정을 정렬이 끝날 때 까지 반복한다.

 

Bubble Sort 구현

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10000

int mknum() {
    int random = (rand() % 100) + 1;
    
    return random;
}

void bubble_sort(int list[], int n) {
    int temp = 0;

    for(int i=0; i<n; i++){
        for(int j=1; j<n-i; j++) {
            if(list[j-1]>list[j]) { //swap
                temp = list[j-1];
                list[j-1] = list[j];
                list[j] = temp;
            }
        }
    }
}

int main() {
    int i;
    int n = MAX_SIZE;
    int list[n];

    printf("Unsorted list :");
    for(i=0; i<n; i++) { //make random list
        list[i] = mknum();
        printf(" %d", list[i]);
    }
    printf("\n");

    //timer
    clock_t start, end;

    start = clock();

    bubble_sort(list, n);

    end = clock();

    printf("Sorted list :");
    for(i=0; i<n; i++) { //print sorted output
        printf(" %d", list[i]);
    }
    printf("\n");

    //run-time result
    printf("Run time : %f\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

 

시간복잡도

---

버블 정렬은 교환 여부에 상관없이 1회차에는 n-1번 계산하고, 2회차에는 n-2번, 마지막에는 1번 계산이 이루어진다. 때문에 시간복잡도는 (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2, 즉 O(n^2)이다. 이는 최악, 최선의 경우에도 마찬가지로 적용된다.

 

공간복잡도

---

주어진 배열에서 교환이 이루어지므로, 추가적인 공간이 필요없다. 때문에 O(n)이다.

 

장점

---

• 매우 간단하고, 직관적이다.
• 추가적인 저장 공간을 요구하지 않으므로, 메모리가 극도로 제한된 환경에서 강력한 이점이 있다.

 

단점

---

• 시간복잡도가 매우 비효율적이다.
• 정렬을 위해서 매우 많은 교환이 이루어진다.