선택 정렬 (Selection Sort) 설명과 JavaScript 예제

선택 정렬은 배열에서 가장 작은 값을 찾아 앞쪽으로 하나씩 정렬해 나가는 단순한 방식의 정렬 알고리즘입니다. 구현이 쉽고 직관적이지만, 성능 면에서는 비효율적이기 때문에 실제 애플리케이션보다는 교육용으로 자주 사용됩니다.

---

1. 동작 원리

1. 배열의 첫 번째 요소부터 시작
2. 남은 요소 중 가장 작은 값을 찾아 현재 위치와 교환
3. 인덱스를 한 칸 뒤로 옮기고 같은 작업 반복
4. 배열의 끝까지 반복하면 정렬 완료

정리하면, "가장 작은 값을 선택해서 앞으로 보낸다"는 의미에서 선택 정렬이라 불립니다.

---

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

function selectionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

console.log(selectionSort([29, 10, 14, 37, 13])); // [10, 13, 14, 29, 37]

• minIndex: 현재 가장 작은 값의 인덱스를 저장
• ES6 구조 분해 할당을 사용하여 값 교환
• 비교는 모든 요소에 대해 반복하지만, 교환은 한 번만 수행

---

3. 시간 및 공간 복잡도

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

• 비교 횟수는 고정: 항상 (n-1) + (n-2) + ... + 1 ≒ O(n²)
• 교환 횟수는 최소화됨: 다른 정렬 알고리즘보다 스왑은 적음
• 공간 복잡도는 O(1) – 추가 메모리 사용 없음

---

4. 선택 정렬의 특징

• 구현이 간단하고 직관적
• 정렬이 완료된 상태와 무관하게 항상 같은 수의 비교 수행
• 작은 데이터셋에서는 사용 가능하나, 대규모 데이터에는 부적합

---

마무리

선택 정렬은 단순하고 명확한 알고리즘으로, 정렬의 개념을 이해하기에 좋은 시작점입니다. 그러나 성능상의 한계로 인해 실제 프로젝트에서는 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등 효율적인 정렬 알고리즘을 사용하는 것이 일반적입니다.

팁: 정렬 알고리즘을 비교할 때는 비교 횟수와 교환 횟수, 공간 복잡도를 함께 고려해야 합니다.