[interview] 선택 정렬 알고리즘에 대해 설명해주세요

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

● 배열에서 정렬되지 않은 부분의 최솟값, 최댓값을 찾아 순서대로 정렬된 부분의 뒤로 옮기는
   방식의 정렬 알고리즘입니다.

 

● 반복문을 사용하여 전체 배열을 순차적으로 정렬하기 때문에 시간 복잡도는
   BigO 기법으로 O(n^2)입니다.

 

선택 정렬 진행 순서

1) 초기화

 - 정렬되지 않은 배열 전체를 대상으로 탐색을 시작합니다.

  [2, 5, 4, 1, 3]

 

2) 최솟값(최댓값) 탐색

  - 배열의 시작 인덱스부터 끝까지 탐색하여 최솟값(최댓값)을 찾습니다.

  [2, 5, 4, 1, 3]

 

3) 스왑(Swap)

  - 찾은 최솟값을 현재 위치의 값과 교환합니다.

  [2, 5, 4, 1, 3] → [1, 5, 4, 2, 3]

 

4) 반복

  - 배열의 다음 요소부터 끝까지 동일한 과정을 반복하여 전체 배열이 정렬될 때까지
    진행합니다.

  [2, 5, 4, 1, 3] → [1, 5, 4, 2, 3] → [1, 2, 4, 5, 3] → [1, 2, 3, 5, 4] → [1, 2, 3, 4, 5]

 

● 정리하자면 
  - 정렬되지 않은 배열 전체를 대상으로 배열의 시작 인덱스부터 끝까지 탐색하여 최솟값(최댓값)
    을 찾고, 최솟값(최댓값)을 찾았을 경우 현재 위치의 값과 교환합니다. 이 과정을 반복하고 배열이
    정렬될 때가지 진행하는 정렬 알고리즘 입니다.

 

JavaScript로 표현해보자면

// 최솟값을 기준으로 정렬
function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 현재 위치에서 최소값의 인덱스를 설정합니다.
    let min = i;
    // i 이후의 요소들 중에서 최솟값을 찾습니다.
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }
    // 만약 최소값이 현재 위치가 아니면 교환합니다.
    if (min !== i) {
      const temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

// 예시 사용
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // 출력: [11, 12, 22, 25, 64]

 

효율적인 알고리즘인가요?

● 구현은 간단하지만 작은 데이터셋에서는 적합하지만, 대규모 데이터셋에서는 굳이 사용할 필요가 없습니다.

   선택 정렬 알고리즘보다 효율적인 다른 알고리즘이 더 많습니다.

 

● 하지만 가장 기본적인 정렬 알고리즘이기 때문에 '정렬은 이런 것이다' 를 이해하기에는 좋은 알고리즘입니다.