정렬 알고리즘 - 삽입 정렬(Insertion Sort)

2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고

지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.

1. 정렬은 2번째 위치(index)의 값을 temp에 저장합니다.
2. temp와 이전에 있는 원소들과 비교하며 삽입해나갑니다.
3. '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복합니다.

시간복잡도는 최악의 경우(역으로 정렬되어 있을 경우) Selection Sort와 마찬가지로,

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 입니다. 하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우,

한번씩 밖에 비교를 안하므로 **O(n)**의 시간복잡도를 가지게 됩니다.

공간복잡도는 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

 

장점

• 알고리즘이 단순합니다.
• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있습니다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않습니다.
• => 제자리 정렬(in-place sorting)
• 안정 정렬(Stable Sort) 입니다.
• Selection Sort나 Bubble Sort과 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠릅니다.

단점

• 평균과 최악의 시간복잡도가 O(n^2)으로 비효율적입니다.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j-1] > arr[j]:
                arr[j-1], arr[j] = arr[j], arr[j-1]