Algorithm - 선택정렬(Selection Sort)

선택정렬이란?

주어진 데이터 중 최소값을 찾아 데이터 맨 앞에 위치한 값과 교체한다. 맨 앞 위치를 뺀 데이터를 동일 방법으로 반복하며 정렬하는 알고리즘

https://visualgo.net/ko/sorting을 참고하면 영상으로 볼 수 있다.

회전을 진행할때마다 최솟값을 탐색한다. 탐색한 최솟값은 정렬이 교체가 되지 않았던 맨앞의 숫자와 교체된다.
더이상 교체가 일어나지 않을때까지 반복한다.

JavaScript

function selectionSort(arr) {
  const length = arr.length;

  for (let i = 0; i < length; i++) {
    let min = i; // 최솟값
    for (let j = i + 1; j < length; j++) {
      if (arr[min] > arr[j]) min = j;
    }
    if (i !== min) {
      let temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
  return arr;
}

console.log(selectionSort([3, 5, 1, 2, 7, 6])); // [1, 2, 3, 5, 6, 7]

첫 번째 for문은 배열의 값을 순차적으로 비교하기 위한 for문이다.
두 번째 for문은 let j = i + 1의 이유는 최솟값이 앞으로 교체했기 때문에 그 이후의 값부터 순회하기 위해서이다.
if (arr[min] > arr[j]) min = j; j가 최솟값보다 작으면 min에 넣어준다.
if (i !== min) 최솟값이 맨 앞 숫자가 아니면 (j가 min이 되었으면) 두 수를 바꿔준다. 최솟값이 그대로면 바꿔주지 않아도 된다.