[인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 4. 삽입정렬

문제

N개이 숫자가 입력되면 오름차순으로 삽입정렬로 정렬

 

풀이

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

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

선택한 숫자와 바로 앞의 숫자와 비교해서 더 작으면 위치를 바꿔준다.

항상 왼쪽이 자기보다 크다는, 즉 ‘정렬이 되어있다'는 가정 하에 탐색을 하므로 만약 자신보다 작은 숫자를 발견하면 거기서 탐색을 멈춘다.