삽입 정렬: Insertion Sort

* Insertion sort?

이미지 출처  https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

삽입 정렬은 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다. 이와 같은 작업을 카드의 수만큼 반복하게 되면 전체 카드가 정렬된다. 이와 같이 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 

 

 

* Pseudocode

 

* 분석

복잡도는 자료 구성에 따라서 달라진다. 입력 자료가 정렬되어 있다면 가장 빠르다. 삽입 정렬의 외부 루프는 n-1번 실행되며 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교 횟수는 n-1번, 총 이동 횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다. 최악의 복잡도는 입력 자료가 역순이라서 각 단계에서 i -1부터 0까지 전부 한 칸씩 밀려나야 하는 경우다. 따라서 외부 루프에서 각 반복마다 i번의 비교가 수행되므로 총 비교횟수는 O(n^2)과 같다. 총 이동 횟수는 외부 루프의 각 단계마다 i + 2번의 이동이 이루어지므로 O(n^2)의 복잡도를 가진다. 

 

레코드의 수가 적을 경우 알고리즘 자체가 간단하여 다른 복잡한 정렬보다 유리할 수 있다. 또한 어느정도 정렬되어 있다면 매우 효율적인 방법이다.

최선: O(n)

최악: O(n ^ 2)