삽입 정렬

"데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다"

필요할 때만 위치를 바꾸면 된다. = 데이터가 거의 정렬 되어 있다면 비용 감소

 

삽입 정렬은 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.

위처럼 정렬이 이루어진 원소는 항상 정렬된 상태를 유지한다.

 

시간 복잡도 : O(N^2)

다만 배열이 거의 정렬되어 있는 경우, 매우 빠르게 동작 (최선의 경우 - O(N) )