삽입 정렬

자신 앞 요소가 자신보다 크면 자기 자리에 앞 요소를 복사하고 앞자리에 자신을 삽입하는 정렬 방식.

const solution = arr => {
    let answer;
    let n = arr.length;

    for (let i = 1; i < n; i++) { // 두 번째 요소부터 검사
        let key = arr[i], j; // i번째 요소를 key라는 변수에 복사해 둠
        for (j = i - 1; j >= 0; j--) { // i-1부터 0까지 검사함
            if (arr[j] > key) { // arr[j](앞 요소)가 복사해둔 key보다 크면
                arr[j + 1] = arr[j]; // 앞 요소를 자기자리에 복사
            } else {
                break; // 앞 요소가 더 작으면 중지
            }
        }

        arr[j + 1] = key; // 검사를 끝낸 후 j+1번째에 key를 삽입함
    }
    return answer;
}

console.log(solution([2, 5, 7, 1, 10, 9]));

j for문 안에서 arr[j] = key를 해도 결과는 같지만 그렇게 하면 검사를 할 때마다 key를 삽입하게 된다.

j for문 밖에서 (검사가 끝난 후) arr[j+1] = key를 하면 올바른 위치에 한번만 삽입하게 된다. 그래서 scope 오류를 피하기 위해 j for 루프 돌기 전에 j를 선언해준다.