[JS] 버블 정렬

1. 버블 정렬

 버블 정렬은 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다. 

 

 첫 번째 원소부터 마지막 원소까지 반복하여 가장 큰 원소가 마지막 자리로 오게 정렬 방식이다.

 

 버블 정렬은 탐색 방법이 선택정렬(이전 포스트 글)과 반대라고 생각하면 된다.

 

 선택 정렬은 처음 요소를 1씩 늘려 탐색하는 방법이라고 한다면,

 

 버블 정렬은 마지막 요소를 1씩 빼서 탐색하는 방법이라고 생각하면 된다.

 

2. 동작 순서

 동작 순서도 크게 어려울 건 없다.

 

 선택정렬(이전 포스트 글)에서 썼던 예시 입력 값을 그대로 써서 설명하도록 하겠다.

 

[그림 1] 입력 값

 

우리는 이제 위의 입력값 [5, 10, 1, 2, 6]을 버블 정렬을 이용하여 오름차순으로 정렬하려고 한다.

 

먼저 첫 요소인 5부터 끝 요소인 6까지 탐색을 실시하여

 

현재 요소 값과 다음 요소 값을 비교하도록 하자.

 

[그림 1] 버블 정렬의 첫 번째 탐색

 

위 그림과 같이 첫 번째 탐색을 끝내면 맨 끝에는 제일 큰 요소 값인 10이 위치하게 된다.

 

아직도 감이 오질 않는다면, 한번 더 탐색을 해보자.

 

이번에는 첫 번째 요소부터 마지막 인덱스-1 의 범위까지 탐색을 해서 비교할 것이다.

 

[그림 2] 버블 정렬의 두 번째 탐색

 

 두 번째 탐색을 완료한 상태이다. 이제 버블 정렬이 어떤 방식으로 동작하는지 확실히 알 수 있을 것이다.

 

 그렇다면, 세번째 탐색은 첫 번째 요소부터 6까지 탐색을 할 것이고

 

 네 번째는 5까지 탐색을 하는 방식으로 돌아갈 것이다.

 

3. 시간 복잡도

위의 예시로 버블 정렬은 총 몇 번의 연산을 했을까?

 

1. [5, 10, 1, 2 , 6]
2. [5, 1, 2, 6] 10
3. [1, 2, 5] 6 10
4. [1, 2] 5 6 10
5. [1] 2 5 6 10

으로 총 5 + 4 + 3 + 2 +1 = 15 번의 연산을 했다는 것을 알 수 있다.

 

따라서, 선택정렬과 마찬가지로 5를 n으로 바꾼다면

$$ \frag{n\times(n+1)}{2} $$

의 결과를 얻게된다.

 

컴퓨터에서는 n이 무지 큰 값으로 가정하기 때문에 2로 나누나 마나 크기 차이가 크게 없어서

 

이를 빅오표기법으로 표기하면

$$ O(n^2) $$

라는 값을 얻게된다.

 

4. 선택 정렬과 버블 정렬 속도 차이

 그렇다면, 선택 정렬과 버블정렬의 속도는 같을까?

 

 답은 선택정렬이 빠르다이다.

 

 왜냐하면 선택 정렬 경우, 탐색을 하면서 최소의 값만 찾아서 스와핑을 하지만

 

 버블 정렬의 경우, 일일히 옆에 있는 값과 계속해서 스와핑을 하기 때문이다.

 

 데이터가 작다면, 속도차이는 크게 없겠지만,

 

 어마어마하게 큰 데이터를 버블정렬을 이용하여 정렬을 한다면?

 

 부하가 정말 만만치 않을 것이다...

 

 굳이 쓴다면 선택 정렬 방식을 이용하는 것을 추천....ㅎㅎㅎ

 

5. 프로그램 코드

 버블정렬의 코드는 다음과 같다.

 

const bubbleSort = (arr) => {
  for(let i=0; i<arr.length; i++){
    let temp = 0;
    // arr.length-1를 해주는 이유는
    // arr.length가 7인경우로
    // 첫번 째 탐색을 실행하면
    // arr[arr.length](11)와 arr[arr.length+1](undefined)를
    // 비교하기 때문이다.
    for(let j=0; j<arr.length-1-i; j++){
      if(arr[j] > arr[j+1]){
        temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

bubbleSort([2, 10, 5, 4, 11,1]);

 

6. 참고 자료

1. 동빈나 - 3강 버블 정렬(Bubble Sort) [실전 알고리즘 강좌(Algorithm Programming Tutorial) #3

2. 자바로 배우는 쉬운 자료구조, 한빛 아카데미