선택 정렬(Selection Sort)

원소 중 가장 작은 값을 선택해 맨 앞에 위치시키는 것을 반복
⇒ 한 루프를 돌면서 최소 값을 찾아 갱신하고 해당 루프가 종료되면 맨 앞자리 요소와 자리 변경

• 버블 정렬과 유사한 알고리즘
• 해당 순서에 원소를 넣을 위치는 정해져있고 어떤 원소를 넣을지 선택하는 알고리즘
• 삽입 정렬(Insertion Sort)와 다른 점은 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는다는 점
• 장점
  • 비교 횟수는 많지만, 교환(Swap) 연산 횟수가 최대 n-1번으로 적음
  • 추가적인 메모리 사용이 거의 없음
• 단점
  • 시간 복잡도가 O(n²)로 데이터 크기가 커질수록 비효율적
  • 이미 정렬된 배열에서도 O(n²) 연산이 필요하여 최적화가 어려움
  • 큰 데이터에는 부적합하며, 작은 데이터에서만 고려할 수 있는 정렬 방법

진행 과정(오름차순 기준)

1. 최소값을 저장할 변수 선언 후 배열의 첫 번째 값을 할당

2. 루프를 돌며 가장 작은 변수 값을 찾아 갱신

   ⇒ 이때 저장하는 것은 최소 값의 값(value)이 아닌 값의 위치(index)

3. 루프가 종료되면 최소 값과 맨 앞자리 요소의 자리를 바꿈

4. 모든 정렬이 완료될 때까지 해당 과정 반복

구현 코드(오름차순 기준)

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]]; // swap
    }
  }

  return arr;
}

// 테스트
const arr = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 최선: O(n²)
  • 평균: O(n²)
  • 최악: O(n²)
• 공간 복잡도
  • O(1)