[기술면접/알고리즘] Insertion Sort

Insertion Sort에 대해 설명하세요

Keyword

key, in-place sorting, 앞 배열 정렬

---

Script

삽입 정렬은 추가적인 메모리 공간을 필요로 하지 않는 in-place 정렬(제자리 정렬) 알고리즘 중 하나로, 매 회전 마다 새로운 원소가 이미 정렬이 되어있는 앞의 배열에서 어느 위치에 들어갈지 계산하여 삽입하는 정렬 알고리즘입니다. 처음 key를 두번째 값으로 시작하여, 앞의 배열이 정렬되어 있기 때문에 뒤에서부터 key 값과의 비교를 통해 위치를 바꾸면서 정렬 기준에 맞도록 자신의 위치를 찾는 방법으로 정렬을 수행합니다. 시간복잡도는 O(n^2)입니다.

---

Additional

시간복잡도

BEST CASE
이미 정렬되어 있는 경우, (n-1)번의 비교만 수행하고 더 이상의 Swap은 없기 때문에,
O(n)

WORST CASE
입력 자료가 역순일 경우

비교 횟수
1회전 - 1번
2회전 - 2번
...
n-1회전 - n-1번
으로, 총 n(n-1)/2

교환 횟수
1회전 - 1번 이동
2회전 - 2번 이동
...
n-1회전 - n-1번 이동
으로, 총 n(n-1)/2 + 2(n-1)

T(n) = O(n^2)

그림

코드 (python)

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]

정렬 알고리즘 시간복잡도 비교