[알고리즘] 버블 정렬

선택 정렬에 이어서 버블 정렬이다.

버블 정렬은 선택 정렬과 마찬가지로 직관적인 해결 방법이다.

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내자

구현은 가장 쉽지만, 가장 비효율적인 알고리즘이라고 할 수 있다.

아래 코드와 실행 결과를 보도록 하자.

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

  for (i = 0; i < 10; i++) {
    console.log(arr[i]);
  }
};

BubbleSort();

버블 정렬 실행 결과

버블 정렬의 구현 방법은 한 번의 정렬이 끝날 때, 가장 큰 값이 가장 뒤로 가게된다.

시간 복잡도 또한 선택 정렬과 똑같이 등차수열을 가지므로
시간 복잡도는 O(N^2)를 가지게 된다.

하지만 선택 정렬보다 약 1.5배 가량 느린 성능을 보여주는데, 왜 그런 것일까?

선택 정렬은 가장 작은 값을 골라서 마지막에만 적용시키지만,
버블 정렬은 반복문이 돌아갈 때마다 자리를 바꾸는 구문을 실행하기 때문에 더 비효율적이라고 할 수 있다.