3.3Selection Sort

Selection Sort

Selection Sort(선택 정렬)는 정렬되지 않은 부분에서 가장 작은 값을 찾아 맨 앞으로 보내는 방식의 정렬 알고리즘이다. 원리는 아래와 같다:

1. 배열의 첫 번째 요소부터 시작하여, 나머지 요소 중 가장 작은 값의 인덱스를 찾는다.
2. 그 인덱스의 값을 현재 위치와 스왑한다.
3. 그다음 위치로 이동하여 같은 작업을 반복한다.
4. 배열이 모두 정렬될 때까지 이 과정을 반복한다.

이 방식은 이전에 살펴본 버블 정렬과 유사한 O(n²) 시간 복잡도를 가지지만, 매 루프마다 스왑을 한 번만 수행한다는 점에서 약간의 차이가 있다. 즉, 루프는 처음부터 끝까지 진행하는 대신 스왑의 수가 적다.

버블 정렬은 인접한 두 값을 매번 비교하면서 정렬하지만, 선택 정렬은 가장 작은 값을 찾아서 한 번에 올바른 위치로 옮긴다.

자바스크립트로는 아래와 같이 구현할 수 있다:

javascript
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);
  }

  return arr;
}

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

• 외부 루프는 정렬 대상 위치를 하나하나 결정하고
• 내부 루프는 가장 작은 값을 찾는다