알고리즘 - 삽입정렬

삽입정렬 (Insert Sort)

- 카드 놀이를 할 때 손에 들고 있는 카드를 정렬하는 것과 유사함

- 오른쪽으로 움직이며 차례로 원소를 적절한 위치에 삽입하고 나머지 원소는 하나씩 오른쪽으로 이동시킴

 

 

 

 

 

 

 

특징

- 레코드를 계속 이동시켜야 하므로 레코드의 크기가 큰 경우에 불리

- 거의 정렬이 된 화일인 경우 유리

- 안정적인 제자리 정렬

- 더미(dummy) 키가 필요함

 

 

 

 

 

 

 

삽입과정

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

수행과정

 

 

     

 

 

 

 

 

 

 

성능 특성

- 시간 복잡도 O(N 2)

- 거의 정렬된 화일의 경우 효율적임