[알고리즘] 정렬 - 버블 정렬(거품 정렬, Bubble Sort) (자바스크립트/javascript/node.js/알고리즘)

버블 정렬(거품 정렬, Bubble Sort)

버블 정렬이란?

버블 정렬은 전체 배열을 순회하면서 항목이 다른 항목보다 큰 경우 두 항목을 교환한다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

 

시간 복잡도

O(n^2)

 

공간 복잡도

O(1)

 

장점

in-place 알고리즘이기 때문에 메모리가 절약된다.

구현하기가 쉽다.

 

단점

다른 정렬 알고리즘은 배열의 이미 정렬된 부분을 활용하는데 비해 거품 정렬은 모든 가능한 짝을 비교하기 때문에 

성능이 안좋은 정렬 중에서도 가장 안좋은 편에 속한다.

 

---

function bubbleSort(array) {
  let temp;
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}
console.log(bubbleSort([5, 4, 3, 2, 1]));

두번째 for문에서 array.length - 1 - i를 하는 이유는, 일단 array[j]와 array[j + 1]을 비교하니까 배열의 마지막 데이터를 포함하지 않아도 검색 대상에 포함되므로 array.length - 1을 해주고, 각 회전이 끝날 때마다 마지막 데이터의 정렬이 끝나기 때문에 i를 빼줘야 한다.