insertionSort

0. 문제

• 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬해 리턴하라.
• number 타입을 요소로 갖는 배열을 리턴해야 한다.
• 삽입 정렬을 구현해라.

1. 주어진 것

• 인자는 number 타입을 요소로 갖는 배열.
• 인자 배열의 길이는 1,000 이하.
• 인자 배열은 중첩되지 않은 1차원 배열.

삽입 정렬

• 삽입 정렬은 요소의 크기를 비교하여 자신의 위치를 찾아 삽입하는 정렬이다.
• 일일이 비교를 하기에 길이가 길면 효율이 떨어진다.

2. 로직

• 결과 배열을 하나 만들고 인자 배열의 0번째 인덱스를 넣는다. (0번째 인덱스를 기준으로 정렬을 시작할 거라서)
• 반복문으로 1번째 인덱스부터 인자 배열을 순회한다.
• 만약 요소가 결과 배열의 인덱스 - 1 요소보다 (왼쪽 요소) 높다면 그냥 push 한다.
• 아니라면, 결과 배열을 0번째 인덱스부터 순회하여 자기 자리를 찾는다. (결과 배열은 정렬된 채로 있기에)
• 자기 자리를 찾았으면 slice를 통해 요소가 들어갈 왼쪽과 오른쪽을 나누고 concat으로 해당 요소를 삽입하여 정렬된 배열을 만든다.

3. 코드

const insertionSort = (arr) => {
  let result = [arr[0]];
  
  for (let n = 1; n < arr.length; n++) {
    //만약 해당 요소가 자기의 왼쪽 요소보다 높다면
    if (arr[n] >= result[n - 1]) {
      result.push(arr[n]);
    } else {
      //결과 배열을 순회해서 자기 자리를 찾자
      for (let i = 0; i < n; i++) {
        if (arr[n] <= result[i]) {
          //자리를 찾았으면 해당 인덱스를 기준 좌, 우를 나눈다.
          let left = result.slice(0, i);
          let right = result.slice(i);
          
          //concat을 사용하여 합치자.
          result = left.concat(arr[n], right);
          break;
        }
      }
    }
  }
  
  return result;
}