[JS] 선택 정렬

선택 정렬은 가장 작은 값을 찾아 첫 번째 요소와 바꾸고 두 번째로 작은 값을 찾아 두 번째 요소와 바꾸는 정렬 알고리즘이다.

첫 번째 요소의 인덱스를 저장한다. 두 번째 요소부터 값을 비교한다.
첫 번째 요소보다 작은 값이 있으면 인덱스를 갱신한다. 인덱스가 갱신되었을 경우에만 값을 바꾼다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIdx] > arr[j]) {
        minIdx = j;
      }
    }
    if (i !== minIdx) {
      [arr[minIdx], arr[i]] = [arr[i], arr[minIdx]];
    }
  }

  return arr;
}

const arr = selectionSort([0, 2, 34, 22, 10, 19, 17]);
console.log(arr);  // [0, 2, 10, 17, 19, 22, 34]

시간 복잡도

최고의 경우: $O(n^2)$
평균의 경우: $O(n^2)$
최악의 경우: $O(n^2)$

공간 복잡도: $O(1)$