[알고리즘] insertionSort

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

삽입 정렬을 구현해야 하며, arr.sort의 사용은 금지된다.

const insertionSort = function (arr) {
  // key는 기준점인 요소이고, compareidx는 비교할 요소의 인덱스이다.
  //key와 바로 왼쪽에 있는 요소를 비교해서 만약 key가 더 작으면 둘의 자리를 바꾼다 
  //위 비교과정은 compareidx가 0이상이고 key보다 compareidx를 인덱스로 가지는 요소가 더 큰 동안만 반복된다. 
  //내부 While문은 반복될 때마다 key와 compareidx도 조정해준다 
  let key;
  let compareidx;
  for(let i=1;i<arr.length;i++){
    key = arr[i]
    compareidx = i-1
      while(compareidx>=0 && arr[compareidx] > key){
        arr[compareidx+1] = arr[compareidx];
        arr[compareidx] = key;
        key = arr[compareidx];
        compareidx--;
      }
  }
  return arr
};

이렇게 구현하면 기본 테스트는 통과가 되지만 callback 함수를 insertionSort 함수의 두번째 인자로 받아서 풀라는 조건에는 부합하지 않는다.

아래 코드에서 transform은 인자를 받아서 그대로 반환하는 함수이다.
사실 왜 인자를 받아서 그대로 반환하는 함수가 필요한지 이해가 가지 않아서 아고라 스테이츠에 질문을 남겼다... 이따 답변 해주시면 내용 추가해야지.

const insertionSort = function (arr, transform = (item) => item) {
  let sorted = [arr[0]];//결과로 반환할 sorted 배열 선언후 arr[0]요소를 배열 안에 넣은채로 할당. 
  for (let i = 1; i < arr.length; i++) {
    if (transform(arr[i]) >= transform(sorted[i - 1])) {
      sorted.push(arr[i]);
    } else {
      for (let j = 0; j < i; j++) {
        if (transform(arr[i]) <= transform(sorted[j])) {
          const left = sorted.slice(0, j);
          const right = sorted.slice(j);
          sorted = left.concat(arr[i], right);
          break;
        }
      }
    }
  }

  return sorted;
};