삽입 정렬

삽입 정렬이란?

'정렬된 부분'안에 '정렬되지 않은 부분'의 데이터들을 정렬 조건에 맞추어 삽입해 나가는 알고리즘

1 단계: 인덱스 0번부터의 값을 tmp(임시변수)에 저장해둔다.
2 단계: j값은 (i-1)~0 까지 순회한다. 
	   (끝까지 순회하게 되면 j = -1값이 됨)
3 단계: 
	if: arr[j] > tmp라면
		1 단계: arr[j+1] = arr[j] 해준다.
		2 단계: 순회를 마친 j(-1)를 j의 뒤 지점(arr[j+1])에 tmp값을 넣어준다.        
    else: break문으로 빠져나온다. 

예시 문제

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;
      // break로 나가게 되면 j값은 j값 그대로 반환된다.
    }
    arr[j + 1] = tmp;
  }
  return answer;
}

let arr = [77, 19, 80];
console.log(solution(arr));