선택 정렬은 가장 작은 값을 찾아서 배열의 맨 앞으로 보내며, 그 다음 작은 값을 찾아나가는 방식으로 정렬하는 알고리즘입니다.

동작 방식

1. 주어진 **배열 중** **최소값**을 찾습니다.
2. 그 값을 맨 앞에 위치한 값과 교체합니다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.

위 과정을 반복하면서 정렬을 수행합니다. 이를 선택 정렬이라고 합니다. 최솟값을 구하기 위해 배열에 전체 요소를 검색하기 때문에 성능적으로 떨어집니다.

시간 복잡도

선택 정렬의 시간 복잡도는 O($n^2$)으로, 정렬하고자 하는 배열의 크기가 커지면 속도가 급격하게 떨어지는 단점이 있습니다.

선택 정렬 예시 코드

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

const arr = [5, 2, 4, 6, 1, 3];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5, 6]