Insertion Sort (삽입 정렬)

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

원소의 개수가 적을 경우 유용하며, 구현이 간단하다.

예제 - [12 11 13 5 6]

두 번째 원소 11을 이전 리스트와 비교하여 적절한 위치에 삽입 -> 11 12 13 5 6 세 번째 원소 13을 이전 리스트와 비교하여 적절한 위치에 삽입 -> 11 12 13 5 6 네 번째 원소 5를 이전 리스트와 비교하여 적절한 위치에 삽입 -> 5 11 12 13 6 마지막 원소 6을 이전 리스트와 비교하여 적절한 위치에 삽입 -> 5 6 11 13 13

코드 - Swift

func insertionSort(var arr : Array<Int>) -> Array<Int> { var i : Int var j : Int var temp : Int var len : Int len = arr.count for i=1; i<len; i++ { temp = arr[i] j = i - 1 while j >= 0 && arr[j] > temp { arr[j+1] = arr[j] j-- } arr[j+1] = temp } return arr } ​ var arr = [12, 11, 13, 5, 6] var result : Array<Int> ​ result = insertionSort(arr) ​ print(result)

시간복잡도

- 최악의 경우 (배열이 정렬 기준 역순으로 되어 있을 경우)  : O(n*n)

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

삽입 정렬 -> 제자리 정렬^[각주:1] 안정 정렬^[각주:2] 온라인 정렬^[각주:3]

참고 1 : http://geeksquiz.com/insertion-sort/

참고 2 : https://ko.wikipedia.org/wiki/정렬_알고리즘

1. 원소들의 갯수에 비해서 충분히 무시할 만한 저장 공간을 사용하는 알고리즘 [본문으로]
2. 중복되는 값이 존재 할 때에 그 값의 순서가 변경되지 않는 알고리즘 [본문으로]
3. 모든 원소들이 처음부터 주어지지 않고 차례대로 들어 오는 경우도 처리할 수 있는 알고리즘 [본문으로]