정렬_ 선택 정렬(Selection Sort)

📒 오늘의 공부

정렬_ 선택 정렬(Selection Sort)

1. 선택 정렬(Selection Sort)

• 간단하고 직관적인 정렬 알고리즘 중 하나
  1. 배열의 첫 번째 원소를 선택한다.
  2. 첫 번째 원소보다 가장 작은 원소를 찾는다.
  3. 가장 작은 원소를 배열의 첫 번째 원소와 교환한다.
  4. 가장 작은 첫 번째 원소를 제외하고 다시 배열에서 가장 작은 원소를 찾아 배열의 두 번째 원소와 교환한다.
  5. 위의 과정을 반복하며 배열을 정렬한다.

2.선택 정렬 구현

• 선택 정렬 코드

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    if (minIndex !== i) {
      console.log(i, minIndex, arr)
      // 최소값과 현재 요소 교환
      const temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }

  return arr;
}

• 예시 문제

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray)

3. 선택 정렬을 사용하는 이유

• 작은 크기의 배열을 정렬할 때: 선택 정렬은 구현이 간단하며 이해하기 쉽기 때문에 작은 크기의 배열을 정렬할 때는 다른 복잡한 정렬 알고리즘보다 빠를 수 있다.

• 원소의 이동 횟수가 중요한 경우: 선택 정렬은 원소를 직접 교환하는 대신 인덱스를 교환하는 방식으로 동작하기 때문에 비교 횟수에 비해 원소의 이동 횟수가 적다.

• 선택 정렬의 시간 복잡도는 항상 O(n^2)이기 때문에 큰 배열에 대해서는 효율성이 떨어질 수 있다.
  

=> '배열의 최솟값을 구하는 문제'의 경우 선택 정렬을 이용할 수도 있지만 Math.min() 메서드와 spread 연산자를 활용하여 간단하게 최솟값을 구할 수 있기 때문에 실제로 프로그래머스 문제를 풀 때 잘 활용하진 않을 것 같다.