본문 바로가기
Language-LAB/Algorithm

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

by JS LAB 2023. 7. 8.
728x90
반응형

삽입정렬

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

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

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

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

 

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)
728x90
반응형