삽입 정렬

정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘

* 타겟인 요소와 이전 위치(이미 정렬된)에 있는 요소들을 비교하여 알맞은 위치를 찾는다.
1. 타겟 요소와 바로 이전 요소와 비교
2. 타겟 요소가 작다면 이전 요소와 교환하고 아니면 종료
3. (교환했다면) 타겟 요소와 교환한 위치의 이전 요소와 비교
4. 타겟 요소가 작다면 교환하고 아니면 종료
5. 하나의 요소의 위치가 정해지면 원래 타겟 요소 다음 위치의 요소로 위 과정을 반복한다.

차례대로 비교/교환하므로 안정적이다.

거의 정렬된 경우에는 (best 상황) n번의 비교만 하고 교환하는 과정이 없으므로, O(N)
역순인 경우 (worst 상황) 타겟 요소가 이전 요소들 중에 제일 작을 것이므로,
타겟 요소를 맨 앞까지 보내야하고, 그 과정을 또 n-1번 해야하니 시간복잡도는 O(N^2)
따라서 평균 시간복잡도도 O(N^2)다.

데이터의 배열 상태에 따라 성능의 차이가 크다!
거의 정렬된 배열에서 좋은 성능을 보인다!

이진 삽입 정렬

타겟 요소가 삽입될 위치를 선형으로 탐색하지 않고 이진 탐색한다!
이전 요소들은 정렬이 되어있는 것을 활용하여 타겟 요소가 하나씩 비교하지 않고,
이진 탐색을 통해 삽입 위치를 탐색한다.
비교에 대한 시간 복잡도는 O(N^2) -> O(NlogN)로 개선될 수 있다.
하지만, 교환에 대한 시간 복잡도는 그대로 O(N^2)이다. 그래서 평균 시간 복잡도는 그대로 O(N^2)이다. 삽입할 공간을 만들기 위해 하나씩 교환하지 않고 블록으로 이동시키면(move함수) O(N)으로 개선이 가능하다

정렬된 경우(best 상황), 일반 삽입 정렬은 O(N)의 시간 복잡도를 보이지만,
구현한 거에 의하면 이진 삽입 정렬은 매 요소 당 삽입 위치를 찾기 위해 이진 탐색을 하므로
매번 logN의 시간비용이 발생한다. 따라서 best일 때 O(NlogN)의 시간복잡도를 갖게 된다.

이를 해결하기 위해 추가로 구현을 하게되면 best 상황에서 O(N)의 시간 복잡도를 가질 수 있다.