Insertion Sort (삽입정렬)

Insertion Sort (삽입정렬)

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘입니다.

O(n^2)의 시간복잡도를 가지지만 선택정렬, 버블정렬 알고리즘에 비해 빠릅니다.

삽입을 할 때 데이터를 하나씩 밀어야 하기 때문에 배열이 길어질수록 효율이 떨어집니다.

Insertion Sort 정렬과정

초기상태: (5 3 4 2 1 7 6)

(5 3 4 2 1 7 6)

(5 3 4 2 1 7 6)

(3 5 4 2 1 7 6)

(3 4 5 2 1 7 6)

(2 3 4 5 1 7 6)

(1 2 3 4 5 7 6)

(1 2 3 4 5 7 6)

(1 2 3 4 5 6 7)

Insertion Sort 코드 (Python)

def insertion_sort(arr):
    length = len(arr)
    for i in range(length):
        j = i - 1
        key = arr[i]
        while arr[j] > key and j >= 0:
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = key
    return arr