[Algorithm] 버블 정렬(bubble sort)

버블 정렬(Bubble sort)이란? 🔫

버블 정렬이란 정렬 알고리즘 중 가장 기본적이고 간단한 알고리즘이며, 배열 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이라고한다. 버블 정렬은 두 인접한 원소를 검사하여 서로의 값을 교환하며 정렬하는 방법인데, 오름차순 정렬의 경우 두 항목의 값을 비교하여 앞쪽값이 더 크면 서로 위치를 교환하고, 내림차순의 경우 그 반대이다.

시간 복잡도

버블 정렬의 시간 최상, 평균, 최악에 상황에도 빅오 O(N^2)로 모두 같으며, 매 회전 시 가장 큰 자료가 맨 뒤로 이동하고 그 다음 회차 시에는 맨 끝의 자료는 정렬에서 제외되는 식으로 매 회전 마다 제외되는 데이터가 하나씩 늘어나기 때문에 (N -1 ... N -2 ... N -3) 총 비교 횟수는 N * ( N - 1) / 2가 된다. 즉 이미 정렬되어있는 상태에서도 매 라운드마다 남은 배열들에서 가장 작은 값을 찾는 불필요한 비교를 진행하기 때문에 다른 정렬 알고리즘에 비해 간단하긴 하지만, 비효율적이라 할 수 있다.

코드

const bubbleSort = function (arr) {
  for (let z = 1; z <= arr.length; z++) {
    for (let i = 0; i < arr.length - (z); i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
      }
    }
  }
  return arr;
};

console.log(bubbleSort([8, 5, 2, 6, 12])) // [2, 5, 6, 8, 12]