Insertion sort

O(n^2)

 

이미 정렬된 데이터 범위에 

정렬되지 않은 데이터를 적절한 위치에 삽입

 

구현하기 쉬움

 

-

 

시행

- 현재 index에 있는 데이터 값을 선택한다

- locked data가 정렬된 데이터 범위에 삽일될 위치를 탐색한다

- 삽입 위치부터 index에 있는 위치까지 shift

- 삽입 위치에 삽입,

- index ++로 커서 옮김

- 전체 데이터의 크기만큼 index가 커질 때까 반복

 

-

 

적절한 삽입 위치를 탐색하는 부분에서 binary search와 같은 탐색 알고리즘을 사용하면 시간 복잡도를 줄일 수 있음