Algorithm : 25 insertionSort

설명

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.

예시

let output = insertionSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]

생각

삽입정렬은 보통 오른쪽으로 순회하던 반복문을 왼쪽으로 순회하면서 기준값 보다 왼쪽 값이 크면 기준값을 해당 값으로 바꾼다. 그 전에 기준값을 다른 변수에 저장해서 왼쪽 값에 재할당한다. 이것을 반복하면 된다.

풀이

const insertionSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  for (let i = 1; i < arr.length; i++) {
    let tmp = arr[i]
    let j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > tmp) {
        arr[j + 1] = arr[j]
      } else {
        break;
      }
    }
    arr[j + 1] = tmp
  }
  return arr
};

깨달은 점

tmp를 설정한 이유는 배열 값이 바뀐 후에 다시 값을 할당해주기 위해 미리 빼놔야 하기 때문이다. 이걸 기억해야 하고 for문이 끝난 후에도 j를 사용해야 하기 때문에 전역변수로 j를 선언하고 for문에서는 j를 선언하면 안되는 스코프 개념을 다시 생각할 수 있었다.