#9 버블정렬(Bubble Sort)

● 도입

- 앞으로 몇 개의 글에서 배열에 무작위로 섞인 숫자를 정렬하는 방법에 대해 알아볼 것이다.

- 이번 글에서는 여러개의 정렬 알고리즘 중 Bubble Sort에 대해 알아볼 것이다.

- Bubble Sort는 가장 쉬운 정렬 알고리즘 중 하나이다.

---

● 개념

- Bubble Sort는 앞에 있는 숫자와 옆에 있는 숫자의 크기를 비교해 자리를 바꾸는 알고리즘이다.

[4, 2, 3, 1]

- 위와 같이 숫자가 무작위로 들어있는 배열이 있다고 했을 때 아래와 같은 작업이 일어난다.

1). 가장 앞에 있는 숫자 4와 그 옆에 있는 숫자 2의 크기를 비교한다.
2). (4 > 2)이므로 4와 2의 자리를 바꾼다.  →  [2, 4, 3, 1]

3). 두 번째 숫자 4와 그 옆에 있는 숫자 3의 크기를 비교한다.
4). (4 > 3)이므로 4와 3의 자리를 바꾼다.  →  [2, 3, 4, 1]

5). 세 번째 숫자 4와 그 옆에 있는 숫자 1의 크기를 비교한다.
6). (4 > 1)이므로 4와 1의 자리를 바꾼다.  →  [2, 3, 1, 4]
------------------------------------------------------------------------------------------------------------------------------------------------------
7). 다시 배열의 (index = 0)부터 위에서 했던 작업을 동일하게 진행한다.
단, 배열의 마지막 원소에는 이미 가장 큰 숫자가 위치했기에 작업 범위에서 제외한다.

8). 가장 앞에 있는 숫자 2와 그 옆에 있는 숫자 3의 크기를 비교한다.
9). (2 < 3)이므로 2와 3의 자리를 바꾸지 않는다.  →  [2, 3, 1, 4]

10). 두 번째 숫자 3과 그 옆에 있는 숫자 1의 크기를 비교한다.
11). (3 > 1)이므로 3과 1의 자리를 바꾼다.  →  [2, 1, 3, 4]

12). 배열의 마지막 원소인 4는 작업 범위에서 제외됐기에 3과 4의 크기는 비교하지 않는다.
------------------------------------------------------------------------------------------------------------------------------------------------------
13). 다시 배열의 (index = 0)부터 위에서 했던 작업을 동일하게 진행한다.
단, 배열의 마지막 원소(4)와 그 이전 원소(3)는 이미 큰 숫자가 차례대로 위치했기에 작업 범위에서 제외한다.

14). 가장 앞에 있는 숫자 2와 그 옆에 있는 숫자 1의 크기를 비교한다.
15). (2 > 1)이므로 2와 1의 자리를 바꾼다.  →  [1, 2, 3, 4]

16). 배열의 마지막 원소인 4와 그 이전 원소인 3은 작업 범위에서 제외됐기에 더 이상 크기를 비교하지 않는다.
------------------------------------------------------------------------------------------------------------------------------------------------------
17). 다시 배열의 (index = 0)부터 위에서 했던 작업을 동일하게 진행한다.
하지만 남은 원소(1)가 하나이므로 더 이상 정렬 작업을 수행할 필요가 없다.

정렬 끝!!!!

- Bubble Sort는 이와 같이 옆의 데이터와 크기를 비교해서 자리를 바꾸는 알고리즘이다.

---

● 실습

function bubbleSort(arr) {
    for (let i = 0; i < (arr.length - 1); i++) { // 배열을 순회할 for문
        for (let j = 0; j < (arr.length - i - 1); j++) { // 각 원소의 크기를 비교하고 자리를 바꿀 for문
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

let arr = [4, 2, 3, 1];
console.log("======= 정렬 전1 =======");
console.log(arr);

console.log("======= 정렬 후1 =======");
bubbleSort(arr);
console.log(arr);

let arr2 = [234, 23, 87, 34, 99, 103];
console.log("======= 정렬 전2 =======");
console.log(arr2);

console.log("======= 정렬 후2 =======");
bubbleSort(arr2);
console.log(arr2);

(arr.length - 1)
- 배열의 개수가 n개라면 자리 교체는 n-1번을 해야 하므로 (arr.length - 1)로 범위 설정
ex)
배열의 개수가 4개라면 자리 교체는 3번을 해야 하므로 (4 -1)로 범위 설정
==========================================================================================
(arr.length - i - 1)
- 배열의 첫번째 원소부터 정렬이 된 원소의 이전 원소보다 하나 이전의 원소까지 순회해야한다.
-i --> 정렬이 된 원소(정렬이 완료된 개수만큼을 i로 빼줘서 범위를 줄여준다.)
-1 --> 정렬이 된 원소의 이전 원소보다 하나 이전의 원소

ex) [3, 2, 1, 4]
- 가장 큰 수인 4가 정렬된 상태라면 (i = 1)이고
- 정렬이 된 원소(4)의 이전 원소(1)보다 하나 이전의 원소(2)까지 순회해야한다.
- 즉, {첫 번째 원소(3) ~ 두 번째 원소(2)}까지 두 번만 순회하면 된다.
- 배열의 길이(4)에서 i 값과 1을 빼면 2번만 반복된다.(4 - i - 1 = 4 - 1 - 1)

---

● 정리

- Bubble Sort는 구현은 쉽지만 성능이 좋다고 할 수는 없다. 이중 반복문을 사용하는 것 자체에서부터 싹수를 알 수 있다.

- Big-O로 Bubble Sort의 성능을 알아보자

---

- 길이가 n인 배열에서 반복문을 한 번씩 돌때마다 마지막 원소가 정렬되는 것을 알 수 있었다.

- 즉, 바깥쪽 for 문이 반복될 때마다 정렬되지 않은 원소 중 가장 큰 원소가 정렬되고 안쪽 for문은 반복 횟수가 점점 줄어든다.(원소가 하나씩 정렬될수록 정렬되지 않은 원소의 개수는 줄어들기 때문)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

 

- 이렇게 원소가 1개만 남을때까지 반복하는데 이를 수학식으로 풀어보면 다음과 같다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 즉, 등차수열의 합과 같다.

- 시간복잡도에서 Big-O는 가장 높은 차수를 선택하고 자연수는 버려야 하기에 결론적으로 Big-O는 O(n^2)가 된다.

cf) 여기에서 자연수는 (1/2) 이다.

- 아래의 그림에서 볼 수 있듯이 O(n^2)은 성능이 좋지 않다. 그렇기에 성능이 중요한 시스템에서 Bubble Sort는 적절치 않을 수 있다.

출처 - 인프런, 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

- 참고로 이렇게 수학적으로 계산하는게 힘들면 "핵심 로직에서 for문 2개가 중첩되니까 대충 O(n^2) 구나"라고
생각해도 된다.
- Big-O는 정확도보다는 데이터가 증가할 때 계산이 늘어나는 척도만 보는 용도이기에 위와 같이 생각해도 무리는 없다.

 

cf)

2023.01.22 - [자료구조 및 알고리즘] - #2 시간복잡도(좋은 알고리즘?) / 최악의 경우는 Big-O

#2 시간복잡도(좋은 알고리즘?) / 최악의 경우는 Big-O