숫자를 요소로 가지는 배열이 주어졌을 때, 그 배열를 삽입 정렬하는 알고리즘을 구현하시오.

(advanced) insertionSort 함수의 두 번째 인자로 callback 함수를 받아서, 그 함수의 리턴값을 기준으로 요소들을 정렬해 보세요.

내가 작성한 코드

advanced 를 통과하기 위해 cb 인자를 하나 더 추가하여 작성하였으나, 테스트 통과가 되지 않았다. 나머지 테스트 케이스가 cb를 인자로 받지 않은 상황에서 테스트를 하도록 설계되었기 때문이다. 이에 아래와 같이 조건문으로 분기를 해주었다.

findIndex를 사용하였으나, 테스트 시간 초과가 되었었는데, 이는 시간복잡도가 O(N)이기 때문이었다.

const insertionSort = function (arr,cb) {
  // TODO: 여기에 코드를 작성합니다.

  //만약에 cb가 undefined라면..
  if(cb === undefined){
    for(let i = 0; i < arr.length ; i++){
      while(arr[i] !== undefined && arr[i - 1] > arr[i]){
        [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
        i--; 
      }
    }
    return arr;
    
  }else if(typeof cb === "function"){
    for(let i = 0; i < arr.length ; i++){
      while(arr[i] !== undefined && cb(arr[i - 1]) > cb(arr[i])){
        [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]];
        i--; 
      }
    }
    return arr;
  } 
};

/*
const cb = (item) => item * item;
insertionSort([-10, -11, 2, 29], cb).should.eql([2, -10, -11, 29]);

콜백함수 실행 시 콜백함수의 리턴값은 [100,121,4,841] => 정렬 결과는 [4,100,121,841]이다.
그래서 원래 숫자로 되돌리면, [2,-10,-11,29]

*/