선택 정렬(Selection Sort)

References

이번 글은 아래 자료들을 참고하여 작성하였습니다.
Section 32. Sort By Selection on Udemy
Selection Sort on Khan Academy

---

Selection Sort

// solution 1.
function selectionSort(arr) {
  for (let i = 0; i < arr.length; ++i) {
    let indexOfMin = i;
    // for문 j 돌면서 arr[j]가 arr[indexOfMin]보다 작으면 indexOfMin을 j로 치환한다. 즉, 현재값과 배열 내 값들을 비교하며, 현재 값보다 작은 값의 위치를 기록하는 것이다.
    for (let j = i + 1; j < arr.length; ++j) {
      if (arr[j] < arr[indexOfMin]) {
        indexOfMin = j;
      }
    }
    // 현재 값보다 작은 값이 배열 내 존재했다면 indexOfMin과 i는 같지 않을 것이고 따라서 큰 값인 현재 값과 작은 값의 위치를 서로 바꿔준다.
    if (indexOfMin !== i) {
      let lesser = arr[indexOfMin];
      arr[indexOfMin] = arr[i];
      arr[i] = lesser;
    }
  }

  return arr;
}

// solution 2.
const swap = function (array, firstIndex, secondIndex) {
  let temp = array[firstIndex];
  array[firstIndex] = array[secondIndex];
  array[secondIndex] = temp;
};

const indexOfMinimum = function (array, startIndex) {
  let minValue = array[startIndex];
  let minIndex = startIndex;

  for (let i = minIndex + 1; i < array.length; ++i) {
    if (array[i] < minValue) {
      minIndex = i;
      minValue = array[i];
    }
  }

  return minIndex;
};

const selectionSort = function (array) {
  let temp;

  for (let i = 0; i < array.length; ++i) {
    temp = indexOfMinimum(array, i);
    swap(array, i, temp);
  }
};

두 solution 모두 주어진 배열을 for문으로 탐색하면서 값들을 하나하나 비교하여 작은 값을 임시 변수에 담고, 더 작은 값이 나오면 임시 변수의 값을 치환하는 식으로 작동하는 코드이다.