선택 정렬 (Selection Sort)

: 선택한 요소와, 나머지 요소 중 가장 작은 요소를 교환하는 정렬 알고리즘

의사 코드

function selectionSort(arr) {
  반복문 (배열을 순회하며) {
    let min = i; 
    "최소값의 인덱스"를 담아둘 변수를 만들고
    일단 i를 할당해두고, 안쪽 반복문 안에서 arr[i]와 나머지 요소들을 비교한다.
    
    반복문 (i를 제외한 나머지 요소들을 순회) {
      만약 (j 번째 요소가 최소값보다 작다면) {
        최소값 인덱스에 j를 저장한다.
      }
      안쪽 반복문이 끝나고나서,
      만약 (최소값 인덱스가 다른 값(j)으로 바뀌었다면) {
        i와 j 두 요소를 스왑해준다.
      }
    }
    
  }
  모든 반복문이 끝났다면 정렬된 배열을 반환한다.
}

풀이

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

선택 정렬은 O(n²)의 시간복잡도를 가진다.

풀면서 궁금했던 점

변수 minIdx에 최소값의 인덱스를 저장하는 게 아니라, 최소값 자체를 저장하면 안되는걸까?

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min = arr[i];
    
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j];
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
  }
  
  return arr;
};

이렇게 코드를 작성해도 결과적으로 정렬은 똑같이 된다.

하지만 첫 번째 풀이는 안쪽 반복문을 순회할 때, min 변수에 인덱스를 업데이트하다 마지막에만 진짜 최소값을 swap해주기 때문에 swap이 1번씩 발생하지만,

두 번째 풀이는 안쪽 반복문을 순회할 때, min보다 작은 값을 만날 때마다 매번 swap해주기 때문에, 더 많은 swap이 발생하고, 그렇기 때문에 더 느리다.

원래 코드

배열의 첫 번째 요소부터 시작한다.

안쪽 배열을 순회하며 최소값을 찾는다.
최소값의 index(=j)를 변수 min에 저장해두었다가, 
arr[i]와 arr[min]두 숫자를 swap한다. (swap 1번)

배열을 모두 순회할 때까지 이 과정을 반복한다.

더 느린 코드

배열의 첫 번째 요소부터 시작한다.

안쪽 배열에서 arr[i]보다 작은 값을 찾을 때마다 두 숫자를 swap한다. (swap 여러 번)
변수 min을 arr[j]로 업데이트한다.

i 배열을 모두 순회할 때까지 이 과정을 반복한다.

출처 : Selection sort: storing value instead of index - Stack Overflow