삽입 정렬

 

 

 

#규칙
1. 왼쪽으로 자기보다 작은 숫자를 만날 때까지 이동
2. 큰 숫자는 우로 이동

삽입 정렬은 배열을 선택하여 해당의 값을 왼쪽의 값과 비교를 해나가고, 자신보다 큰 수는 우측으로 이동을 시킨다. 그런 후, 자기보다 작은 값 또는 0번째 배열이 나오게 되면 비어있는 자리에 저장을 하게 된다.

삽입 정렬은 거품 정렬처럼 swap을 해나가는 것이 아니다.

ex)

8    7    9    4    10    5
  <-7

7    8    9    4    10    5
       <-9

7    8    9    4    10    5
             <-4

4    7    8    9    10    5
                   <-10

4    7    8    9    10    5
                          <-5

4    5    7    8    9    10

 

알고리즘