[Sort] Bubble sort

첫 번째로 가져온 건 bubble sort 입니다.

Bubble sort는 정렬되는 모습이 수면 위로 올라오는 거품과 비슷해 붙여진 이름입니다.

https://favtutor.com/resources/images/uploads/mceu_61632030011682402256084.png

그림을 보면 다음과 같습니다.

각 pass에서 작은 key가 점차 올라오는 것을 볼 수 있습니다.

인접한 key를 비교하여 바꾸는 방법으로 정렬됩니다. 

이 방법은 작은 key부터 왼쪽으로 정렬하는 반면,

큰 key부터 오른쪽으로 정렬하는 방법도 있습니다.

그 2가지 경우의 코드를 모두 봐보겠습니다.

 

- 작은 key부터 왼쪽으로 정렬

// list: given unsorted array, n: number of elements
void bubbleSort_ver1(int list[], int n){
    cout << "< Bubble Sort_1 >" << endl;

    cout << "unsorted list: ";
    for (int index=0; index<n; index++) cout << list[index] << " ";
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "[Pass " << i+1 << "]" << endl;
        for (int j = n-1; j > i; j--) {
            if (list[j] < list[j - 1]) {
                // swap elements
                cout << "swap: " << list[j] << ", " << list[j - 1] << endl;
                int temp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = temp;

                for (int index=0; index<n; index++) cout << list[index] << " ";
                cout << endl;
            }
        }
    }

    cout << endl << "sorted list: ";
    for (int index=0; index<n; index++) cout << list[index] << " ";
    cout << endl;
}

 

 

- 큰 key부터 오른쪽으로 정렬

// list: given unsorted array, n: number of elements
void bubbleSort(int list[], int n){
    cout << "< Bubble Sort >" << endl;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (list[j] > list[j + 1]) {
                // swap elements
                cout << "swap: " << list[j] << ", " << list[j + 1] << endl;
                int temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;

                for (int index=0; index<n; index++) cout << list[index] << " ";
                cout << endl;
            }
        }
    }

    cout << endl << "sorted list: ";
    for (int index=0; index<n; index++) cout << list[index] << " ";
    cout << endl;
}

 

 

이 두 방법의 큰 차이점은 중첩 반복문입니다.

작은 key부터 왼쪽으로 정렬	큰 key부터 오른쪽으로 정렬
for (int i = 0; i < n; i++) {         for (int j = n-1; j > i; j--) {             if (list[j] < list[j - 1]) {                 int temp = list[j];                 list[j] = list[j - 1];                 list[j - 1] = temp;             }         }     }	for (int i = 0; i < n; i++) {         for (int j = 0; j < n - i - 1; j++) {             if (list[j] > list[j + 1]) {                 int temp = list[j];                 list[j] = list[j + 1];                 list[j + 1] = temp;             }         }     }

 

이 두 부분을 보면 index가 다르다는 것을 알 수 있습니다.

작은 key부터 정렬하는 방법은 뒤에서부터 배열을 탐색하기 때문에, 두 번째 반복문의 index가 맨 뒤에서부터 시작합니다.

그리고 현재 key와 그 앞 key를 비교하면서, 만약 현재 key가 더 작다면 교환하여 앞으로 이동하는 형식입니다.

 

큰 key부터 정렬하는 방법은 앞에서부터 배열을 탐색하기 때문에, 두 번째 반복문의 index가 맨 앞에서부터 시작합니다.

그리고 현재 key와 그 뒤 key를 비교하면서, 만약 현재 key가 더 크다면 교환하여 앞으로 이동합니다.

 

그 출력 결과도 비교해 볼까요?

1) 왼쪽: 작은 key부터 왼쪽으로 이동 2) 오른쪽: 큰 key부터 오른쪽으로 이동

 

같은 입력이지만 그 과정이 다르다는 것을 볼 수 있습니다.

 

시간복잡도도 살펴봅시다.

중첩 반복문으로 정렬하기 때문에, 가장 좋지 않고 평균적인 시간복잡도는 $O(n^2)$ 이라는 것을 알 수 있습니다.

만약 모두 정렬되어 있는 배열이 입력된다면, 가장 좋은 경우가 되고 이때의 시간 복잡도는 $O(n)$ 입니다.

---

오늘은 bubble sort에 대해 알아보았습니다. 다음은 selection sort를 정리해보겠습니다.