[정렬] 삽입 정렬 (Insertion Sort)

삽입 정렬 설명

1. 두 번째 요소를 선택한다.
2. 그 값을 key로 저장해서, 그 앞에 있는 요소들과 크기 비교한다.
3. 앞쪽 값(들)이 key보다 크면, 한 칸씩 오른쪽으로 복사(밀기)한다.
4. key값이 들어가야 할 위치가 나오면, 그 자리에 key를 삽입한다.
5. 이를 n-1번째(마지막) 요소까지 반복한다

시간복잡도

최선의 경우 : 매번 한번씩만 비교 시 -> O(n)

 

최악의 경우 : 1 + 2 + 3 + .... + (n-2) + (n-1) = n(n-1)/2 이므로 -> O(n^2)

장점

•  요소들의 수가 적으면 알고리즘이 단순해서 다른 복잡한 정렬 알고리즘보다 유리
• 어느정도 요소들이 정렬되어 있으면 시간 단축됨

단점

• 요소들의 수가 많은 경우에 적합하지 않음
• 다른 알고리즘들에 비해 요소의 이동이 잦음