손 안의 카드를 정렬하는 방법과 유사합니다.
Insertion Sort는 Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘입니다.
Insertion Sort는 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.
최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 상요될 만큼 좋은 정렬 알고리즘입니다.
def insertion_sort(arr):
for end in range(1, len(arr)):
for i in range(end, 0, -1):
if arr[i - 1] > arr[i]:
arr[i - 1], arr[i] = arr[i], arr[i - 1]
최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로, (n-1) + (n-2) + ... + 2 + 1 => n(n-1)/2
즉, O(n^2) 입니다.
하지만, 모두 정렬이 되어있는 경우, 한번씩 밖에 비교를 안하므로 O(n)의 시간복잡도를 가지게된다. 또한 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문입니다.
최선의 경우는 O(n)의 시간복잡도를 갖고, 평균과 최악의 경우 O(n^2) 의 시간복잡도를 갖게 됩니다.
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.