Sort - Insertion Sort (삽입정렬)

알고리즘 > 정렬 > 삽입정렬

원소가 들어갈 위치를 찾아서 맞는 자리에 삽입하는 방법.

 n개의 원소에 대하여 n개의 메모리 사용

 최선의 경우 : 원소들이 이미 정렬되어 있는 경우 O(n)

 최악의 경우 : 원소들이 역순으로 되어있는 경우  O(n^2)

                                                             평균 시간복잡도 : O(n^2)