삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
시간 복잡도 O(n^2)로 느린편이지만 구현이 쉽다.
선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위체 삽입
과정
현재 index에 있는 데이터 값 선택
현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치 탐색
삽입 위치부터 index에 있는 위치까지 shift 연산 수행
삽입 위치에 현재 선택한 데이터를 삽입하고 index++연산 수행
전체 데이터 크키만큼 index가 커질 때까지, 즉 선택할 데이터가 없을때까지 반복
