삽입정렬(Insertion sort)

삽입정렬이란?

자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치에 삽입하는 정렬

구체적인 개념

• 두 번째 자료부터 시작하여 그 앞의 자료들과 비교하여 삽입할 위치를 지정후 자료를뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘
  

특징

• 장점
  • 안전한 정렬방법
  • 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬방법보다 유리할 수 있다.
  • 대부분 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
• 단점
  • 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

시간복잡도

• O(n^2)