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

삽입정렬

앞에서부터 순서대로 보면서

 앞에 있는 모든 원소가 정렬이 되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬

축소 정복 전략 알고리즘이며

정렬된 리스트에서 항목 삽입 위치 찾기가 핵심!

 

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


n = int(input())
elements = list(map(int, input().split()))


insertion_sort(elements)


print(*elements)