정렬 알고리즘 - 버블 정렬

버블 정렬(Bubble Sort)

• 서로 인접한 두 원소를 비교하며 순서대로 정렬하는 알고리즘(여기선 오름차순 기준 정렬)

시간복잡도

• 최선의 경우 : O(n), 이미 정렬이 되어있는 경우
• 최악의 경우 : O(n^2): 정렬이 하나도 안되어있는 경우

장점

버블 정렬은 in place 알고리즘이기 때문에 메모리가 절약된다는 장점이 있다. 여기서 "in place"라는 것은 자료를 정렬할 때 추가적인 메모리 공간이 필요한 것이 아니고 데이터가 저장된 그 공간 내에서 정렬을 한다는 뜻이다.

또한 구현하기 매우 쉽다는 장점도 있다. 그 외에도 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수도 있다.

단점

버블 정렬의 가장 큰 단점은 자료의 개수가 많아질수록 성능이 매우 떨어진다는 점이다. 왜냐면 최악의 경우 O(n^2)이 소요되기 때문이다. 만약 데이터가 위 이미지처럼 5개밖에 없다면 최대 25번 순회를 해야하지만 데이터가 1,000개라면 1,000,000번이나 순회를 해야한다.

구현

'use strict';

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

    if (!swap) break;
  }

  return arr;
}

const array = [5, 4, 3, 2, 1];
console.log(BubbleSort(array));