Insertion sort

삽입정렬 작성에 필요한 생각의 변화를 작성하고, 구현을 진행한다.

기본규칙

1) sorted list 와 unsorted list 를 둔다.
2) unsorted list 에서 첫번째 값을 선택한다.
3) sorted list 의 끝에서부터 선택원소와 비교 swap 한다.
4) unsorted list 가 빌 때까지 j-- 방향으로 반복한다.

생각의 변화

i는 0이 아니라 1부터 시작한다.

원소가 아니라 인덱스만 보관한다.
루프가 종료되면 j를 더 줄일 필요가 없다.

i를 사용해 sorted list 를 표현한다

pseudo code

for i=1  i<=n-1  i++
    j=i
    while j>0  &&  A[j-1]>A[j]
        swap j-1 j
        j--

검증

12 25 64 11 22
   ij
      ij
         ij

swap j-1 j

12 25 11 64 22
      j

swap j-1 j

12 11 25 64 22
   j

swap j-1 j

11 12 25 64 22
            ij

swap j-1 j

11 12 25 22 64
         j

swap j-1 j

11 12 22 25 64
      j

      stop

시간복잡도