[알고리즘 with JS] 선택 정렬 (selection sort)

선택 정렬은 가장 작은 값을 찾아 맨 앞에 위치하는 인덱스와 교환한다.

가장 작은 값을 찾는 게 루프 하나를 돈 것이고, 정렬된 데이터는 누적된다.

 

선택 정렬에서 중요한 점으로 3가지가 있다.

- 최솟값 저장할 변수 생성 (처음에는 시작값에 대입)

- 다음 항목과 비교해 가며 더 작은 값이 있다면 최솟값 변수에 저장 (실제값이 아닌 인덱스 값)

- 루프 하나 돌면 시작 인덱스와 최솟값 인덱스 교환

 

선택 정렬과 버블 정렬의 차이점으로는
버블 정렬은 다음 원소와 비교하여 swap을 하며 진행하면서 가장 큰 값을 마지막으로 밀어내지만,

선택 정렬은 최솟값을 찾아 마지막에 교환한다는 것이다.

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

위 코드에서 if (i !== min) 은 시작 인덱스와 min 값이 같다면 최솟값이 가장 앞에 있는 것이므로,
i와 min 값이 다를 때만 교환하기 위해 작성해 준 조건문이다.

 

swap 수가 최소이거나, swap 수를 고려할 경우 버블 정렬보다 선택 정렬을 사용하는 것이 좋다.