[Sorting] 삽입 정렬, Insertion Sort

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 삽입 정렬 (Insertion Sort)

• 리스트가 정렬된 부분과 정렬되지 않은 부분으로 나뉘며, 정렬되지 않은 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하는 방식의 정렬 알고리즘
• 리스트의 첫번째 원소를 현재 원소로 지정하여 정렬을 시작하고, 리스트의 마지막 원소를 이미 정렬되어 있는 앞부분에 삽입했을 때 정렬을 마침

Insertion Sort 출처 위키피디아

- 수행 시간

• 입력에 민감한(Input sensitive) 알고리즘으로, 입력이 거의 정렬되어 있을 때 정렬이 매우 빠르고, 입력이 역으로 정렬되어 있을 때가 최악 경우로서 매우 느림
• 입력이 정렬되어 있을 경우 n - 1회 비교하면 정렬을 마치지만, 최악 경우에는 선택 정렬과 같은 O(n^2) 소요
• 입력 데이터의 순서가 무작위인 경우, 삽입 정렬의 평균 수행 시간 또한 O(n^2)
• 실제 응용에서는 이미 정렬된 파일 뒷부분에 소량의 신규 데이터를 업데이트 하는 경우에 활용, 재귀호출을 하지 않으며 프로그램이 간단하여 우수한 성능을 보임