1. 삽입정렬이란? Insertion sort 삽입정렬(Insertion sort)이란, 단어 그대로 삽입(insertion)을 이용한 정렬이라고 할 수 있다. 정렬하고자 하는 대상인 키와 정렬된 키들의 목록이 주어지면, 키를 정렬 순서가 유지되도록 삽입하는 것을 말한다. 즉, 삽입 정렬이란 정렬하고자 하는 원소를 key로 설정한 뒤 그 앞의 정렬된 목록과 비교해가면서 어느 위치에 들어가게 될지를 결정하는 정렬을 말한다고 할 수 있다. 만약 사이즈가 n인 어레이가 주어지면, 삽입정렬에서는 두 번째 원소부터 정렬을 시작하게 된다. 두 번째 원소부터 시작하는 이유는 삽입 정렬을 하기 위해서는 정렬의 대상이 되는 key와 정렬이 들어갈 수 있는 정렬된 목록이 필요하기 때문인데, 첫 번째 원소를 key로 설정하..
