선택 정렬 (Selection Sort) 알고리즘

1. 선택 정렬이란?

선택 정렬(Selection Sort)은 배열에서 가장 작은 값을 찾아 차례대로 정렬하는 방식의 정렬 알고리즘이다. 단순하지만 비효율적인 정렬 방법 중 하나이다.

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

정렬은 데이터 검색과 같은 다양한 연산을 더 빠르게 수행할 수 있도록 해준다. 선택 정렬은 개념이 단순하여 학습 목적으로 많이 사용된다.

3. 선택 정렬의 동작 과정

1. 배열에서 가장 작은 요소를 찾는다.
2. 해당 요소를 맨 앞의 요소와 교환한다.
3. 나머지 부분 배열에서 위 과정을 반복하여 정렬을 완료한다.

4. 선택 정렬의 수식 표현

선택 정렬의 시간 복잡도는 항상 O(n^2)이다.

• 총 비교 횟수:

  $\sum_{i=1}^{n-1} (n - i) = \frac{n(n-1)}{2}$

  즉, O(n^2)

5. Dart 코드 구현

void selectionSort(List<int> arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // Swap
    int temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

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

6. 실행 결과

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

7. 선택 정렬의 장단점

장점

• 개념이 단순하고 이해하기 쉬움
• 추가적인 메모리 공간을 거의 사용하지 않음

단점

• 시간이 오래 걸림 (O(n^2))
• 데이터 크기가 커질수록 비효율적

8. 마무리

선택 정렬은 효율적이지 않지만, 정렬 알고리즘을 학습하는 데 적합하다. 이후에는 퀵 정렬, 병합 정렬 같은 효율적인 알고리즘을 배우는 것이 좋다.