[코플릿]insertionSort

문제

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

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr.length는 1,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 삽입 정렬을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

Advanced

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

 

 

 

풀이

---

const insertionSort = function (arr, callback) {
  let result = arr.slice(); // 주어진 배열을 복사하여 result에 저장합니다.

  if (callback) {
    result = result.map((el) => callback(el)); // callback 함수가 주어졌을 경우, 
    //배열 요소를 callback 함수의 반환값으로 변환합니다.
  }

  for (let i = 1; i < result.length; i++) {
    let key = result[i]; // 현재 삽입될 요소인 i번째 요소를 key 변수에 저장합니다.
    let originalKey = arr[i]; // key에 해당하는 원본 배열의 요소도 저장합니다.
    let j = i - 1;

    while (j >= 0 && result[j] > key) {
      result[j + 1] = result[j]; // key보다 큰 요소들을 한 칸씩 뒤로 이동시킵니다.
      arr[j + 1] = arr[j]; // 원본 배열도 같은 방식으로 이동합니다.
      j--;
    }

    result[j + 1] = key; // 알맞은 위치에 key를 삽입합니다.
    arr[j + 1] = originalKey; // 원본 배열에도 삽입합니다.
  }

  return arr;
};

• result에다가 주어진 배열을 복사하고, 콜백함수가 있을 경우, map으로 callback 함수의 반환값으로 변환합니다.
• result를 이용해서 삽입정렬을 진행합니다. callback함수의 경우, 변형된 배열로 반환되기에 원본을 result의 맞춰서 똑같이 배열의 위치를 변경하게 만듭니다.
• 다만 이럴 경우, 원본 훼손의 우려가 있기에 arr를 따로 silce해서 원본을 유지하는 것이 좋습니다.