선택 정렬(Selection Sort)

선택 정렬(Selection Sort)은 주어진 배열에서 최솟값을 선택하여 정렬하는 알고리즘이다.

자바스크립트로 구현해보기

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;

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

    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }

  return arr;
}

const array = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(array);
console.log(sortedArray); // [11, 12, 22, 25, 64]

위 코드는 주어진 배열을 오름차순으로 정렬하는 선택 정렬의 구현이다. 알고리즘은 배열을 순회하면서 최솟값을 찾아 현재 위치와 교환하는 과정을 반복한다.

시간 복잡도

선택 정렬의 시간 복잡도는 이중 for문을 사용하기 때문에 항상 O(n^2)이다.

선택 정렬은 비교 연산의 횟수가 많아 큰 규모의 데이터에 대해서는 효율적이지 않은 정렬 알고리즘이라고 볼 수 있다.