버블 정렬 (Bubble Sort) 알고리즘

1. 버블 정렬이란?

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 정렬하는 가장 기본적인 정렬 알고리즘 중 하나이다. 정렬할 리스트의 크기가 클수록 성능이 떨어지지만, 개념이 단순하여 학습 목적으로 자주 사용된다.

2. 알고리즘이 필요한 이유

컴퓨터에서 데이터를 효과적으로 정렬하는 것은 매우 중요하다. 정렬된 데이터를 사용하면 검색, 탐색, 데이터 분석 등의 연산이 훨씬 효율적으로 수행될 수 있다. 버블 정렬은 단순한 알고리즘이지만, 정렬의 기본 개념을 이해하는 데 유용하다.

3. 버블 정렬의 동작 과정

1. 리스트의 처음부터 시작하여 인접한 두 개의 요소를 비교한다.
2. 앞의 요소가 뒤의 요소보다 크면 서로 위치를 교환한다.
3. 리스트의 끝까지 이 과정을 반복하면 가장 큰 요소가 리스트의 끝으로 이동한다.
4. 위 과정을 리스트의 크기만큼 반복하여 전체 리스트를 정렬한다.

4. 버블 정렬의 수식 표현

버블 정렬의 시간 복잡도는 최악, 평균 모두 O(n^2)이며, 최선의 경우(이미 정렬된 배열)에는 O(n)이다.

• 총 비교 횟수:
  $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$
  즉, O(n^2)

5. Dart 코드 구현

void bubbleSort(List<int> arr) {
  int n = arr.length;
  bool swapped;
  for (int i = 0; i < n - 1; i++) {
    swapped = false;
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;
      }
    }
    // 정렬이 완료되었으면 종료
    if (!swapped) break;
  }
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];
  print("정렬 전: \$numbers");
  bubbleSort(numbers);
  print("정렬 후: \$numbers");
}

6. 실행 결과

정렬 전: [64, 34, 25, 12, 22, 11, 90]
정렬 후: [11, 12, 22, 25, 34, 64, 90]

7. 버블 정렬의 장단점

장점

• 개념이 단순하고 이해하기 쉬움
• 추가적인 메모리 공간을 거의 사용하지 않음 (제자리 정렬, in-place sorting)

단점

• 시간이 오래 걸림 (O(n^2))
• 큰 데이터셋을 정렬하는 데 비효율적

8. 마무리

버블 정렬은 비효율적인 알고리즘이지만, 정렬 알고리즘을 배우는 첫 단계로 적합하다. 이후에는 퀵 정렬, 병합 정렬 등 더 효율적인 알고리즘을 학습해보는 것이 좋다!