| 삽입정렬 개념 | 삽입정렬 알고리즘 | 삽입정렬 분석 |

삽입 정렬 알고리즘

 

-------------------------------------------

procedure INSERT(R,n)

     for j ← 2 to n do

          R ← Rj

          K ← Kj

          i  ← j-1

          while i >0 and Ki > K do

               Ri+1 ← Ri

               i ← i-1

          end

          Ri+1 ← R

     end

end INSERT

-------------------------------------------


 ■ n=5일 때, 입력 레코드에 대한 삽입 정렬 과정

 초기 상태

30

15

20

17

40

 

 j=2

 15

30

20

17

40

 

 j=3

 15

20

30

17

40

 

 j=4

 15

17

20

30

40

 

 j=5

 15

17

20

30

40

     (정렬 완료)