Bubble Sort

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 필요한 경우 위치를 교환하는 정렬 알고리즘이다. 배열의 요소들을 순차적으로 비교하며 정렬을 수행한다.

자바스크립트로 구현해보기

function bubbleSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    for (let j = 1; j < arr.length; j++) {
      if (arr[j] < arr[j - 1]) {
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
  }

  return arr;
}

// 테스트
let numbers = [5, 3, 8, 4, 2];
console.log(bubbleSort(numbers)); // [2, 3, 4, 5, 8]

1. 5 3 8 4 2 인접한 5와 3을 비교해서 오름차순으로 정렬해준다.

2. 3 5 8 4 2 다음으로 인접한 5와 8을 비교하는데 이미 정렬이 되어있기 때문에 그대로 두고 다음으로 넘어간다.

3. 3 5 8 4 2 다음으로 인접한 8과 4를 비교해서 오름차순으로 정렬해준다.

4. 3 5 4 8 2 반복해서 끝까지 순회한다.

5. 이중 for문이기 때문에 모든 요소가 정렬될 때까지 반복해서 동작한다.

시간복잡도

Bubble Sort의 시간 복잡도는 O(n^2)다. 이는 배열의 크기에 제곱에 비례하여 연산 횟수가 증가한다는 의미다.

배열의 크기가 커질수록 연산 횟수가 기하급수적으로 증가한다. 이러한 이유로 큰 규모의 데이터에 대해서는 효율적이지 않은 정렬 알고리즘이라고 볼 수 있다.

대학생 시절 시험 문제로 나와서 직접 손으로 여러번 작성했던 기억이 있다.😭