삽입 정렬 - Insertion Sort

내 풀이

function solution(arr) {
  let answer = arr;
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] <= arr[j - 1]) [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      else break;
    }
  }
  return answer;
}

let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));

좀 bubble sort 스럽게 구현한 것 같다.
Solution 풀이1 을 보면 조금 더 효과적으로 삽입하는 아이디어가 있다

Solution 풀이1

function solution(arr) {
  let answer = arr;
  for (let i = 0; i < arr.length; i++) {
    let tmp = arr[i],
      j;
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > tmp) arr[j + 1] = arr[j];
      else break;
    }
    arr[j + 1] = tmp;
  }
  return answer;
}

let arr = [11, 7, 5, 6, 10, 9];
console.log(solution(arr));

뭔가 저렇게 절묘하게 j가 -1이 되면 0에 넣어주는 발상을 했다는 것이 참 신기하다..

Solution 풀이2

      function solution(arr) {
        let answer = [];
        answer.push(arr[0]);
        for (let i = 1; i < arr.length; i++) {
          for (let j = 0; j < answer.length; j++) {
            if (arr[i] < answer[j]) {
              answer.splice(j, 0, arr[i]);
              break;
            }
          }
        }
        return answer;
      }

      let arr = [11, 7, 5, 6, 10, 9];
      console.log(solution(arr));

arr[i]가 answer[j]보다 작아진 순간 그 뒤에 삽입해주는 idea이다.
이것도 좀 신기하다. 배워놔야겠다.