거품정렬(Bubble Sort)

목표

• Bubble Sort 정의
• Bubble Sort 과정
• Bubble Sort을 구현
• Bubble Sort의 시간복잡도

정의

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다.
(한번 순회할 때마다 마지막 하나가 정렬되는 모습을 거품에 비유)

원리도 직관적이라서 구현하기 편하긴 하지만 꽤나 비효율적인 정렬 방식이다. 그래서 보통 처음 배울 때 한번 짜보고 나면 실무에서 쓰는 경우는 거의 못 본다고 한다.
(이미 정렬된 자료에 대해서는 1번만 순회하면 되기때문에 최선의 성능을 보여준다.)

구현

function bubbleSort (input) {
  const len = input.length;
  let tmp = null;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (input[j] > input[j + 1]) {
        // Swap
        tmp = input[j];
        input[j] = input[j + 1];
        input[j + 1] = tmp;
        tmp = null;
      }
    }
  }
  return input;
}

시간복잡도

시간복잡도를 계산하면, (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2이므로, O(n^2) 이다. 또한, Bubble Sort는 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.