JavaScript로 알아보는 선택 정렬(Selection Sort)과 예제 코드

소개

주어진 리스트에서 가장 작은 값을 선택하여 맨 앞에 위치시키고, 그다음으로 작은 값을 찾아 두 번째 위치에 위치시키는 과정을 반복하여 정렬하는 알고리즘입니다.

앞으로 보내진 원소는 더 이상 위치가 변경되지 않습니다.

기본 개념

선택 정렬은 간단하면서도 이해하기 쉽고 코드 구현이 쉬운 알고리즘이지만, 그만큼 시간 복잡도가 높아 대규모 데이터를 정렬할 때는 성능이 떨어지는 단점이 있습니다.

선택 정렬의 시간 복잡도는 O(N^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) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArr = [3, 1, 6, 2, 9, 0];
const sortedArr = selectionSort(unsortedArr);
console.log(sortedArr); // [0, 1, 2, 3, 6, 9]

1. 배열의 길이를 변수 n에 저장한 뒤, 바깥쪽 for loop에서 i를 0부터 n-2까지 증가시킵니다.
2. 현재 인덱스 i부터 끝까지의 값 중 가장 작은 값을 찾아 i번째 위치에 놓습니다.
3. 이 과정을 n-1번 반복하면 모든 값이 정렬되어 나열됩니다.