Insertion sort

개요

부분 데이터 [math]\displaystyle{ a_i ~ a_n }[/math] 이 주어진 경우 그중에서 최소항을 찾아서 그 값과 [math]\displaystyle{ a_i }[/math] 와 교화하는 과정을 처음 부터 끝가지 시행하는 방식을 직접 선택법이라 한다.

알고리즘

i 가 0~n-1 인 상황에서,

1. 대상 항 i 를 0 부터 n-2 까지 옮기며 다음을 반복한다.
2. 대상 항을 최소값의 초기값으로 설정한다.
3. 대상 항 + 1 부터 끝가지중 최소항을 찾는다.
4. 최소항과 대상항 i 를 교환한다.