핵심이론
선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심
수행방식
현재 인덱스에 있는 데이터 값을 선택한다
현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색한다
삽입위치부터 인덱스에 있는 위치까지 shift 연산을 수행합니다
삽입 위치에 현재 선택한 데이터를 삽입하고 인덱스 ++연산을 수행합니다
전체 크기에 대해 위 과정을 반복합니다
삽입정렬에서 시간복잡도를 줄일 수 있는 부분은 선택된 데이터가 들어갈 위치를 탐색하는 부분이며 이진탐색을 통해 탐색에 대해서만 logN의 시간복잡도를 가질 수 있지만 이후 shift 하는 연산에서 매우 큰 시간복잡도가 발생합니다
시간복잡도
정렬된 범위에 대해 위치를 찾는 시간복잡도는 O(N) 에서 binary search를 사용하게 되면 O(logN) 까지 줄일 수 있습니다
그리고 이 탐색을 N개의 데이터에 대해 수행하여야 하므로
총 O(N^2) 만큼의 시간복잡도가 발생할 수 있습니다 (binary search 사용시 O(logN) )
