🧮

Bubble Sort

Bubble Sort - Explanation

보통 알고리즘 O(n²) O(n)

Problem Summary

Implement bubble sort to sort an array in ascending order.

Go to Problem →

Detailed Explanation

이 문제는 **버블 정렬(Bubble Sort)** 알고리즘을 학습합니다. 가장 이해하기 쉬운 정렬 알고리즘이지만 효율성은 낮습니다. **버블 정렬의 원리** 인접한 두 요소를 비교하여 순서가 잘못되면 교환합니다. 큰 값이 "거품처럼" 배열 끝으로 떠오르는 것처럼 보여서 버블 정렬이라고 합니다. **알고리즘 동작** 1. 첫 번째 요소부터 시작하여 인접한 요소와 비교 2. 앞의 요소가 더 크면 교환 3. 배열 끝까지 반복하면 가장 큰 요소가 맨 뒤로 감 4. 정렬되지 않은 부분에 대해 반복 **[64, 34, 25, 12, 22] 첫 번째 패스** - [64, 34] → 교환 → [34, 64, 25, 12, 22] - [64, 25] → 교환 → [34, 25, 64, 12, 22] - [64, 12] → 교환 → [34, 25, 12, 64, 22] - [64, 22] → 교환 → [34, 25, 12, 22, 64] 64가 맨 뒤로 이동! **최적화 팁** 내부 루프에서 교환이 없으면 이미 정렬된 것이므로 조기 종료할 수 있습니다. **왜 n-i-1까지만 반복하는가?** i번의 패스 후에 마지막 i개의 요소는 이미 정렬되어 있으므로 다시 비교할 필요가 없습니다.

Solution Code

solution.js
function bubbleSort(arr) {
  const result = [...arr];
  const n = result.length;

  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (result[j] > result[j + 1]) {
        [result[j], result[j + 1]] = [result[j + 1], result[j]];
      }
    }
  }
  return result;
}

Key Concepts from This Problem

1. 버블 정렬 알고리즘
2. 인접 요소 비교
3. 배열 요소 교환
4. 이중 반복문

Common Mistakes

✗ 원본 배열을 직접 수정하면 부작용이 생길 수 있습니다
✗ 내부 루프 범위를 n까지 하면 배열 범위를 벗어납니다
✗ 최적화 없이 이미 정렬된 배열도 O(n²) 시간이 걸립니다

Hints

Hint 1: 인접한 두 요소를 비교합니다.
Hint 2: 큰 값을 오른쪽으로 이동시킵니다.
Hint 3: 이중 반복문을 사용하세요.

Complexity Analysis

Time Complexity

O(n²)

Proportional to the square of input size

Space Complexity

O(n)

Uses memory proportional to input size

Related Tags

#알고리즘 #정렬 #버블정렬
Solve Problem Other Problems