[Javascript] Selection Sort (선택 정렬) 구현 코드

Selection Sort (선택 정렬)

현재값과, 현재값을 제외한 이후 요소 중 최소값을 비교한 후 스왑하는 정렬이다.
버블정렬이 최대값을 뒤로 밀어내는 방식이었다면 선택정렬은 최소값을 앞으로 보내는 방식이라 할 수 있다.
다만 버블정렬이 인접한 두 요소를 비교하는 방식이었다면,
선택정렬은 최소값을 '선택'한 후 비교하기 때문에 선택정렬이라는 이름이 붙었다.

수도코드

1. 이중 반복문을 선언한다
  2. 첫 번째 반복문 : 현재값 i를 순회하는 반복문
  	2-1. 최소값의 인덱스를 담을 변수를 선언한다. 초기값은 현재값 i
  	3. 두 번째 반복문 : 비교값 j를 순회하는 반복문
  	  3-1. 최소값과 비교값을 비교한 후 더 작은 수의 인덱스를 최소값 변수에 할당한다
  4. 두 번째 반복문이 끝난 후 최소값의 인덱스와 i를 비교한다
  	4-1. 두 인덱스가 같지 않다면 스왑한다.
5. 정렬된 배열을 리턴한다.

코드구현

const arr = [1, 9, 8, 16, 5, 2, 7, 3];

// swap 헬퍼 함수
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]];
  return arr;
}

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

const result = selectionSort(arr);
console.log(arr); // [1, 2, 3, 5, 7, 8, 9, 16]