선택정렬 구현

문제

주어진 배열 외에 다른 배열을 생성하지 않고,
선택정렬 알고리즘을 구현하여
배열 내 원소를 오름차순으로 정렬해본다.

예시

Input	Output
[13, 5, 11, 7, 23, 15]	[ 5, 7, 11, 13, 15, 23 ]

풀이 및 회고

• 선택정렬은 주어진 배열 내 원소 중 최소값을 찾아 배열 맨 앞의 값과 교체하는 알고리즘이다.
• 두 번째 교체부터는 이미 교체되었던 앞의 값을 제외한 최소값을 찾아야 한다.
• 풀이 초반에는 임시 배열을 추가로 만들어서 기존 배열에서 최소값을 찾아낼 때마다 임시 배열에 삽입하는 방식으로 풀려고 했다.
• 그러나 배열을 새로 만드는 건 메모리 관리 차원에서 아쉽다는 생각이 들었다.
• 대신 별도의 pointer 변수를 만들어서, 이미 값이 교체되었던 원소를 최소값 산출에서 무시하게끔 처리했다.

코드

const solution = (nums) => {
  let pointer = 0;
  while (pointer < nums.length) {
    const minIdx = getMinIdx(nums, pointer);
    [nums[pointer], nums[minIdx]] = [nums[minIdx], nums[pointer]];
    pointer++;
  }
  return nums;
};

const getMinIdx = (arr, pointer) => {
  let minIndex;
  arr.reduce((min, num, i) => {
    if (min > num && i >= pointer) {
      minIndex = i;
      return (min = num);
    } else return min;
  }, Infinity);
  return minIndex;
};