삽입정렬(Insertion Sort)

*삽입 정렬(Insertion Sort) ->삽입 정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다. ->2번째 원소부터 n번째 원소부터 차례로 각 원소가 맞는 위치에 '삽입'하는 방식을 사용하며 배열을 정렬하기 때문에 삽입 정렬이라고 이름지었다. ※사람에게 어떤 대상을 정렬하라고 한다면 무의식적으로 수행하는 정렬 방식이라고 한다!

*삽입 정렬의 이해 ->어떤 대상을 '오름차순'으로 정렬할 때 삽입 정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고, n번째 원소까지 이 방식을 반복함으로써 정렬을 진행할 수 있다. 예를 들어 [6, 2, 3, 4, 1]이라는 배열을 삽입 정렬을 이용하여 오름차순 정렬을 해보면 다음과 같다.

초기 배열 상태. Array[CurIndex]는 임시 변수에 저장하여 값을 기억해둔다.

현재 선택된 원소의 앞 원소와 비교를 하며 현재 원소의 적절한 위치를 찾는...