선택 정렬(Selection Sort)

선택 정렬이란?

정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환하면서 정렬하는 방식

맨 앞 요소를 기준으로 정하고 나머지 요소들과 비교하면서 최솟값을 찾은 뒤 최솟값을 맨 앞의 요소와 위치를 바꾸면서 정렬하는 개념이라고 할 수 있다.
위치 교환이 자주 일어나는 버블 정렬과 달리 순회 마지막에 위치를 바꾼다는 차이점이 있는 것 같다.

과정은 다음과 같다.

1. 맨 앞 요소를 임의로 최솟값으로 지정한다.
2. 나머지 요소들과 비교하면서 보다 작은 값이 있으면 해당 값을 최솟값으로 지정한다.
   (이때, 루프 중 최솟값 갱신이 일어나지 않으면 굳이 위치를 바꾸지 않아도 되기 떄문에 위치를 바꾸는 작업은 갱신이 일어났을 때만 하면 된다.)
3. 한 반복이 끝나면 최솟값을 맨 앞의 요소와 위치를 바꾼다.
4. 맨 앞부터 정렬하기 때문에 다음 반복마다는 반복 횟수를 줄일 수 있다.

선택 정렬 구현

function selectionSort(arr) {
  const swap = (arr, idx1, idx2) =>
    ([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

  for (let i = 0; i < arr.length; i++) {
    let lowest = i;

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

    if (i !== lowest) swap(arr, i, lowest);
    // 위 코드와 동일
    // let temp = arr[i];
    // arr[i] = arr[lowest];
    // arr[lowest] = temp;
  }

  return arr;
}

selectionSort([34, 22, 10, 19, 17]); // [10, 17, 19, 22, 34]

선택정렬과 빅오 복잡도

선택정렬은 엄청나게 효율적이지는 않다. 배열의 길이가 길어지면 비교 횟수도 n의 제곱에 비율로 늘어나기 떄문이다.
버블정렬은 매 순회마다 가장 큰 값을 끝에 도달할 때까지 계속 스왑이 발생한다. 하지만 선택정렬은 반복하여 여러 번 비교하지만 각 루프가 끝날 때 한번만 스왑하게 된다.
어떤 이유로 메모리에 쓰는 것을 고려하거나, 실제 스왑을 수행하는 것을 고려한다면 이 경우에는 선택정렬이 낫다고 할 수 있다.(아주 흔한 경우는 아니지만)