버블 정렬 (Bubble Sort) 설명과 JavaScript 예제

버블 정렬은 가장 간단하고 직관적인 정렬 알고리즘 중 하나입니다. 인접한 두 요소를 비교하여 크기 순서가 맞지 않으면 자리를 바꾸는 방식으로 정렬을 수행합니다. 데이터가 거의 정렬되어 있을 경우에는 빠르게 동작하지만, 대부분의 경우 성능이 떨어져 실제 사용보다는 교육용으로 자주 활용됩니다.

---

1. 동작 원리

버블 정렬은 다음 과정을 반복합니다:

1. 배열의 처음부터 끝까지 인접한 두 요소를 비교
2. 앞의 값이 뒤의 값보다 크면 두 값을 교환
3. 위 과정을 배열의 끝까지 반복
4. 한 번 순회가 끝날 때마다 가장 큰 값이 맨 뒤로 '버블처럼' 올라감

이를 전체 길이 - 1 만큼 반복하면 정렬이 완료됩니다.

---

2. JavaScript 예제 - 오름차순 정렬

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 값 교환 (swap)
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

console.log(bubbleSort([5, 3, 8, 4, 2])); // [2, 3, 4, 5, 8]

• len - 1 - i: 매 반복마다 가장 큰 값이 뒤로 가므로 비교 범위를 줄입니다.
• ES6의 구조 분해 할당을 이용해 간결하게 값을 교환합니다.

---

3. 성능 분석

구분	시간 복잡도
최선의 경우	O(n)
평균	O(n^2)
최악의 경우	O(n^2)

• 최선의 경우는 이미 정렬되어 있는 배열 (단, 개선된 버전에서만 O(n))
• 공간 복잡도는 O(1): 추가 메모리 사용이 없음

---

4. 개선된 버전 (Early Exit)

function bubbleSortOptimized(arr) {
  const len = arr.length;
  let swapped;
  for (let i = 0; i < len - 1; i++) {
    swapped = false;
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 이미 정렬된 경우 반복 중단
  }
  return arr;
}

console.log(bubbleSortOptimized([1, 2, 3, 4, 5])); // [1, 2, 3, 4, 5]

• 정렬이 이미 완료된 경우, 불필요한 반복을 건너뛰어 성능 향상

---

마무리

버블 정렬은 이해와 구현이 간단하지만, 시간 복잡도 때문에 대용량 데이터를 다루기엔 비효율적입니다. 그러나 정렬 알고리즘의 기초 개념을 익히기에 매우 좋은 예제입니다.

학습용으로는 좋지만, 실제 프로젝트에서는 Array.prototype.sort() 또는 빠른 정렬(Quick Sort), 병합 정렬(Merge Sort) 등의 고급 정렬을 사용하는 것이 권장됩니다.