[정렬] 삽입정렬(Insertion Sort)

특징

• 구현이 간단하다
• 제자리 정렬이다
• 안정 정렬이다.
• 시간 복잡도가 O(n^2)으로 느리다.

 

기본 아이디어

i는 1부터 시작하여 n-1까지 늘려간다. array[0]부터 array[i-1]까지 정렬되어 있을 때, array[i]를 포함하여 정렬한다.

array[i]를 뒤에서부터 순차적으로 array[i-1], array[i-2] ... 과 비교하다가 자기보다 작은 숫자가 나오면 그 뒤에 삽입한다. 아래 영상 참고

www.youtube.com/watch?v=OGzPmgsI-pQ

 

비교연산은 1 + 2 + 3 + ... + (n-1) 회 일어나고, 스왑 연산의 횟수도 비교 연산과 같으므로 시간 복잡도는 O(n^2)

파이썬 코드

def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        while i > 0 and array[i-1] > key:   # array[k]가 key보다 작다면 더이상 비교하지 않고 반복문 탈출. 왜? array[i]까지는 이미 정렬된 배열이기 때문 
            array[i] = array[i-1]
            i -= 1
        array[i] = key