Algorithm

2. Bubble Sort(버블정렬)

버블정렬의 정렬방식

오늘 우리가 알아볼 정렬방식 그 두번째는 버블정렬(Bubble sort)이다.
버블정렬은 어떠한 수들의 배열(array)이 있을 때 자신의 오른쪽(혹은 왼쪽)에 있는 값과 비교하여 작은 값을 앞으로 보내어 정렬하는 방식이다.

여기서 앞으로 보낸다는 뜻은 비교된 두 값 중 작은 값을 왼쪽으로 이동시킨다는 것을 의미한다.

예를들어

arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9]라는 배열이 있다면 10(=== arr[0])과 1(=== arr[1])을 비교한다.
1(=== arr[1])가 10(=== arr[0])보다 작으므로 1(=== arr[1])과 10(=== arr[0])의 자리를 바꾼다.
그렇게 하면 1(=== arr[0])은 10(=== arr[1])이 되고, 배열은 arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]이 된다.
다시 10(=== arr[1])와 5(=== arr[2])을 비교하면 5(=== arr[2])이 작으므로 두 값을 위치를 바꾼다.
그러면 arr = [1, 5, 10, 8, 7, 6, 4, 3, 2, 9]이 된다.
이런식으로 arr[8]과 arr[9]까지의 비교 후 자리 바꿈을 끝내면 arr = [1, 5, 8, 7, 6, 4, 3, 2, 9, 10]이 된다.

이 과정을 통해 arr[0]부터 arr[8]까지의 값들 중 arr[9]보다 큰 값은 이제 없다.
다시 arr[0]과 arr[1]의 비교 후 자리 바꿈, arr[1]과 arr[2]의 비교 후 자리 바꿈, ···, arr[7]과 arr[8]의 비교 후 자리 바꿈을 진행하면
arr = [1, 5, 7, 6, 4, 3, 2, 8, 9, 10]가 된다.
이 과정을 통해 arr[0]부터 arr[7]까지의 값들 중 arr[8]보다 큰 값은 이제 없다.
이러한 과정을 총 10번 반복하게 되면 정렬된 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 될 것이다.

버블정렬의 코드화

위에서 정리한 내용을 토대로 버블정렬을 코드화 해보도록 하자.

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
}

먼저 정렬하고자 하는 arr를 선언한다.

그 후, 위에서 기술한 버블정렬의 정렬방식을 토대로 싸이클을 생각해보면

1. i = 0, arr[0]과 arr[1]의 비교부터 arr[8]과 arr[9]의 비교까지
2. i = 1, arr[0]과 arr[1]의 비교부터 arr[7]과 arr[8]의 비교까지
3. i = 2, arr[0]과 arr[1]의 비교부터 arr[6]과 arr[7]의 비교까지
   ···
4. i = 9, arr[0]과 arr[0]의 비교

위와 같이 반복되는 것을 알 수 있다.

arr[j]와 arr[j+1]를 비교하며 j값을 점점 늘려나가는데 한 싸이클을 돌 때 마다(== i값이 1씩 증가할 때 마다)
arr[9 - i]값은 이 배열 내에서 가장 큰 값이 되므로 다음 싸이클에서는 이를 무시해도 된다.
따라서 이를 토대로 반복문을 작성해보면

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
    for (let i = 0; i < 10; i++) {
        for (let j = 0; j < 9 - i; j++) {
            // something
        }
    }
}

위와 같이 표현할 수 있으며, 이제 남은 것은 선택정렬을 배울 때 사용했던 swapping뿐이다.
오직 arr[j] > arr[j+1]일때만 swapping이 이뤄지므로 if문을 사용하여

{
    let arr = [10, 1, 5, 8, 7, 6, 4, 3, 2, 9];
    for (let i = 0; i < 10; i++) {
        for (let j = 0; j < 9 - i; j++) {
            if (arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            else {
                continue;
            }
        }
    }
    console.log(arr);
}

위와 같이 작성하게 되면 버블정렬도 끝이 난다.

console.log(arr); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

버블정렬의 Big O 표기법

우리가 오늘 배운 버블정렬에서의 채택한 정렬방법은 인접한 두 값을 살펴본 후 작은 값을 앞으로 보내는 것을 반복하는 정렬이다.
따라서 오늘 우리가 예시로 들었던 n = 10의 경우에는

1. i = 0 일때, 인접한 값 9쌍의 값을 살펴봄 --> 9회
2. i = 1 일때, 인접한 값 8쌍의 값을 살펴봄 --> 8회
3. i = 2 일때, 인접한 값 7쌍의 값을 살펴봄 --> 7회
   ···
4. i = 9 일때, 인접한 값 1쌍의 값을 살펴봄 --> 1회

즉 입력 n = 10일때, 연산과정은 1회 + 2회 + ··· + 9회 = 45회가 된다.
선택정렬때 사용했던 등차수열의 합의 공식을 대입하면 결국 입력 n에 대한 연산과정은 (n+(n+1))/2회이며,
상수들을 모두 제거하면 O(n) = n ** 2 즉, O(n ** 2)임을 알 수 있다.

Summary

Bubble Sort(버블정렬)의 정렬방식은 인접한 두 값을 살펴본 후 작은 값을 앞으로 보내는 것을 반복하는 정렬이다.
가장 뒤로 보내진 값은 모든 값들 중 가장 큰 값이므로 다음 값들을 살펴볼 때에는 이를 제외하고 살펴봐도 무방하다.
앞으로 원소를 보낸다는 것은 두 원소의 자리를 바꾼다는 의미인데 이를 위해 Swapping이라는 기법을 사용하며, 여기서는 Temporal Variable Swapping기법을 사용하였다.
Big O notation(빅오표기법)은 굉장히 큰 n의 입력이 들어왔을 때 가장 최악의 복잡도를 갖게 될 경우 몇 번의 연산 과정(O(n))을 거치는지에 관한 표기법이므로
오늘 살펴본 버블정렬의 복잡도는 또한 선택정렬과 마찬가지로 O(n ** 2)이다.

Reference

• Youtube : Algorithm Programming Tutorial - by Dongbin Na
• 4 Ways to Swap Variables in JavaScript
• Swapping Items in an Array