[정렬 알고리즘] 버블정렬

버블정렬

- 버블정렬는 선택정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

- 시간복잡도는 O(n^2) 이다. 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

 

 

버블정렬은 이웃한 2개의 숫자끼리 비교하면서 서로 바꿔주는 것이다.

앞선 선택정렬과 동일하게 이중 반복문을 이용하면 된다.

 

간단한 오름차순 문제를 풀어보자

   function solution(arr) {
        let answer = arr;

        for (let i = 0; i < arr.length - 1; i++) {
          for (let j = i; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
              [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
          }
        }

        return answer;
      }

      let arr = [13, 5, 11, 7, 23, 15];
      console.log(solution(arr));

arr[j] > arr[j+1] 과 같이 앞과 뒤를 비교하는 것이기 때문에 0부터 n까지 돈다고 반복된다고 할 때 반복문 둘 다 n-1까지만 탐색하면 된다.

 

여기서 개선을 더 하고자 한다면

j는 arr.length-1-i를 하면 된다. 이미 정렬이 되어있는 부분까지는 확인하지 않아도 되기 때문이다.

 

그림 예시를 보면 이해하기 쉽다.

 

이중 반복문이 1번 돌 때 다음과 같이 배열이 변화된다.

5 13 11 7 23 15

5 11 13 7 23 15

5 11 7 13 23 15

5 11 7 13 15 23

젤 뒤에가 큰 숫자가 맨 뒤에 위치하는 것을 확인할 수 있다.

즉 버블정렬은 맨 뒷 자리부터 정렬이 된다.

 

장점으로는 구현이 매우 간단하고, 소스코드가 직관적이다.

하지만 시간복잡도가 최악, 최선, 평균 모두 O(n^2)이기에 비효율적이다.