daily 알고리즘 : insertionSort

소히·2022년 7월 14일

Insertion_Sort 삽입정렬 알고리즘

알고리즘Daily

목록 보기

2/22

insertionSort

문제

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

입력

인자 1 : arr

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

출력

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

주의사항

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

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

입출력 예시

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

풀이

arr의 첫번째 인덱스 값으로 초기 배열을 생성하고 비교를 시작한다.
arr의 오른쪽 값과 왼쪽값을 비교하여 삽입할 위치를 정하고 splice 메서드로 삽입한다.

const insertionSort = function (arr, callback = (el) => el) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [arr[0]]; // 값을 비교하기 위해 초기 배열 생성해준다. [3]
  for (let i = 1; i < arr.length; i++) {
    // 만약 arr의 오른쪽값이 왼쪽값보다 클 경우에는 바로 푸시해준다.
    if (callback(arr[i]) > callback(result[i - 1])) {
      result.push(arr[i]);
    } else {
      // 만약 아닐경우에는
      for (let j = 0; j < result.length; j++) {
        if (callback(arr[i]) <= callback(result[j])) {
          // let left = result.slice(0, j);
          // let right = result.slice(j);
          // result = left.concat(arr[i], right);
          result.splice(j, 0, arr[i]);
          // result 배열의 어떠한 값보다 arr[i]가 작을 때 그 사이에 값을 넣어준다!
          break; // 해결 되었으니 break 걸어줘야 한다.
        }
      }
    }
  }
  return result;
};