[알고리즘][파이썬/Python] 삽입 정렬 (Insertion Sort)

정의

정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방식의 정렬 알고리즘

 

동작 방식

0. 정렬할 배열(혹은 리스트)은 두 개의 부분집합 S와 U로 구분

* S (Sorted) : 정렬된 앞부분의 원소들

* U (Unsorted) : 아직 정렬되지 않은 나머지 원소들

1. U의 가장 앞에 있는 원소를 꺼내어 S의 마지막 원소부터 첫 번째 원소까지 대소 비교하며, S 내에 적절하게 삽입될 위치를 탐색

2. 대소 비교가 끝나면, U에서 꺼낸 원소를 탐색한 위치에 삽입

3. 그 결과, S의 원소는 하나 증가하며 U의 원소는 하나 감소

4. U가 공집합이 될 때까지 위 과정을 반복하며 정렬

 

메모리 사용 공간

n개의 원소에 대하여 n개의 메모리 사용

 

연산 시간

1. 최선의 경우 (Best Case) : 자료가 이미 정렬되어 있는 경우

- 전체 비교횟수 : 바로 앞자리 원소와 한 번만 비교하므로, n - 1 번

 

2. 최악의 경우 (Worst Case) : 자료가 역순으로 정렬되어 있는 경우

- 전체 비교횟수 : 1 + 2 + 3 + ... + (n - 2) + (n - 1) = n(n - 1) / 2

 

∴ 시간 복잡도 T(n) = O(N^2)

 

소스 코드

# 삽입 정렬 (Insertion Sort)

# 삽입 정렬 - 오름차순 (Insertion Sort - Ascending)
def insertionSort_ASC(arr):
    n = len(arr)
    for i in range(1, n):
        val = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] > val:
            arr[pos] = arr[pos-1]
            pos -= 1
        arr[pos] = val
    return arr  

# 삽입 정렬 - 내림차순 (Insertion Sort - Descending)
def insertionSort_DESC(arr):
    n = len(arr)
    for i in range(1, n):
        val = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] < val:
            arr[pos] = arr[pos-1]
            pos -= 1
        arr[pos] = val
    return arr  

# # 난수를 생성하여 test해보기 (Test by random number)
from random import randint

lst = [randint(1, 101) for i in range(5)]
print('Insertion Sort(ASC) :', lst, end=' '); print('->', insertionSort_ASC(lst))
# Insertion Sort(ASC) : [68, 82, 21, 96, 88] -> [21, 68, 82, 88, 96]

lst = [randint(1, 101) for i in range(5)]
print('Insertion Sort(DESC) :', lst, end=' '); print('->', insertionSort_DESC(lst))
# Insertion Sort(DESC) : [39, 70, 7, 7, 99] -> [99, 70, 39, 7, 7]

그나마 앞서 포스팅한 버블 정렬과 선택 정렬에 비해서 Best Case(즉, 배열이 전부 정렬되어 있는 경우) 일 때의 시간 복잡도가 O(N)이라는 장점이 있다. 그러나 역시 시간 복잡도 T(n)에 대한 Big-O Notation은 Worst Case를 기준으로 하는 것이 일반적이므로, 안타깝지만 삽입 정렬 또한 그리 효율적이지는 못하다고 볼 수 있다.

 

코드를 통해 알고리즘 흐름 알아보기

추가적으로, 그림으로 설명하고 싶지만 그림을 그릴 만큼의 시간은 허락되지 않아 코드로 삽입 정렬의 흐름을 자세하게 보여주고자 코드를 약간 변경해봤다. 아래 코드로 알고리즘의 흐름을 이해하는 데에 많은 도움이 되었으면 좋겠다.

def insertionSort_ASC(arr):
    n = len(arr)
    for i in range(1, n):
        print('\n{}번째 loop 시작\n'.format(i))
        print('S =', arr[:i], 'U =', arr[i:], '\t# {}번째 loop에서 정렬 전'.format(i))
        val = arr[i]
        pos = i
        while pos > 0 and arr[pos-1] > val:
            arr[pos] = arr[pos-1]
            print('S =', arr[:i], 'U =', arr[i:])
            pos -= 1
        if pos == i:
            pass
        else:
            arr[pos] = val
            print('S =', arr[:i], 'U =', arr[i:])
        print('S =', arr[:i+1], 'U =', arr[i+1:], '\t# {}번째 loop에서 정렬 후'.format(i))
    print('\n정렬 종료')

from random import randint
lst = [randint(1, 51) for i in range(7)]
insertionSort_ASC(lst)

# 1번째 loop 시작

# S = [29] U = [14, 44, 36, 7, 33, 15]    # 1번째 loop에서 정렬 전
# S = [29] U = [29, 44, 36, 7, 33, 15]
# S = [14] U = [29, 44, 36, 7, 33, 15]
# S = [14, 29] U = [44, 36, 7, 33, 15]    # 1번째 loop에서 정렬 후

# 2번째 loop 시작

# S = [14, 29] U = [44, 36, 7, 33, 15]    # 2번째 loop에서 정렬 전
# S = [14, 29, 44] U = [36, 7, 33, 15]    # 2번째 loop에서 정렬 후

# 3번째 loop 시작

# S = [14, 29, 44] U = [36, 7, 33, 15]    # 3번째 loop에서 정렬 전
# S = [14, 29, 44] U = [44, 7, 33, 15]
# S = [14, 29, 36] U = [44, 7, 33, 15]
# S = [14, 29, 36, 44] U = [7, 33, 15]    # 3번째 loop에서 정렬 후

# 4번째 loop 시작

# S = [14, 29, 36, 44] U = [7, 33, 15]    # 4번째 loop에서 정렬 전
# S = [14, 29, 36, 44] U = [44, 33, 15]
# S = [14, 29, 36, 36] U = [44, 33, 15]
# S = [14, 29, 29, 36] U = [44, 33, 15]
# S = [14, 14, 29, 36] U = [44, 33, 15]
# S = [7, 14, 29, 36] U = [44, 33, 15]
# S = [7, 14, 29, 36, 44] U = [33, 15]    # 4번째 loop에서 정렬 후

# 5번째 loop 시작

# S = [7, 14, 29, 36, 44] U = [33, 15]    # 5번째 loop에서 정렬 전
# S = [7, 14, 29, 36, 44] U = [44, 15]
# S = [7, 14, 29, 36, 36] U = [44, 15]
# S = [7, 14, 29, 33, 36] U = [44, 15]
# S = [7, 14, 29, 33, 36, 44] U = [15]    # 5번째 loop에서 정렬 후

# 6번째 loop 시작

# S = [7, 14, 29, 33, 36, 44] U = [15]    # 6번째 loop에서 정렬 전
# S = [7, 14, 29, 33, 36, 44] U = [44]
# S = [7, 14, 29, 33, 36, 36] U = [44]
# S = [7, 14, 29, 33, 33, 36] U = [44]
# S = [7, 14, 29, 29, 33, 36] U = [44]
# S = [7, 14, 15, 29, 33, 36] U = [44]
# S = [7, 14, 15, 29, 33, 36, 44] U = []  # 6번째 loop에서 정렬 후

# 정렬 종료