[알고리즘] 삽입 정렬 (Insertion Sort) 이란?

삽입 정렬 (Insertion Sort) 란?

손 안의 카드를 정렬하는 방법과 유사하다.

2번째 원소부터 시작하여 그 앞(왼쪽) 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

 

 

과정 (오름차순)

1. 정렬은 2번째 위치의 값을 temp에 저장한다.

2. temp와 이전에 있는 원소들과 비교하여 이전 값이 더 큰 경우 이전 값을 오른쪽으로 한 칸씩 이동하다가 그렇지 않은 경우 temp를 삽입한다.

3. 1번으로 돌아가 다음 위치의 값을 temp에 저장하고 반복한다.

 

 

Python Code

def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        temp = arr[i]
        prev = i-1
        while prev >= 0 and arr[prev] > temp: # 이전 원소가 temp보다 크면 오른쪽으로 이동시킨다.
            arr[prev+1] = arr[prev]
            prev -= 1

        arr[prev+1] = temp # temp보다 큰 값을 모두 왼쪽으로 이동시킨 후 값을 삽입한다.
    
    print(arr)

insertion_sort([5,4,3,2,1])

1. 첫 번째 원소 앞에는 원소가 없기 때문에, 두 번째 위치부터 탐색을 시작한다. temp에 i번째 값을 저장하고, prev에는 i 위치 이전의 위치(i-1)를 저장한다.

2. i-1를 가리키는 prev가 음수가 되지 않고, i-1값이 1번에서 선택한 temp보다 크다면, 왼쪽으로 이동시키고 prev를 -1하여 이전 위치를 가리키도록 한다.

3. 2번에서 반복문이 끝나고 나면 prev 위치의 값은 temp보다 작다는 의미이므로 prev+1 위치에 temp를 삽입한다.

 

 

시간복잡도

최악의 경우 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)이다.

 

 

장점

- 알고리즘이 단순하다.

- 대부분의 원소가 정렬되어 있는 경우, 효율적일 수 있다.

- 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

- Selecton Sort나 Bubble Sort와 같은 O(n^2) 알고리즘에 비교하여 상대적으로 빠르다.

 

 

단점

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