삽입 정렬 알고리즘

삽입 정렬 알고리즘(insertion sort algorithm) 삽입 정렬(insertion sort)은 리스트를 반복하면서 각 항목을 이미 정렬된 부분 리스트의 올바른 위치에 "삽입"함으로써 동작합니다. 리스트의 두 번째 항목에서 시작하여 왼쪽의 항목과 비교합니다. 현재 항목이 왼쪽 항목보다 작으면 왼쪽 항목을 오른쪽으로 이동시킵니다. 이를 현재 항목이 왼쪽 항목보다 크거나 왼쪽에 더 이상 항목이 없을 때까지 반복합니다. 그런 다음 현재 항목을 마지막으로 비어 있는 위치에 삽입합니다. 이 과정을 리스트의 모든 항목에 대해 반복합니다. 이를 파이썬 코드로 구현하면 다음과 같습니다: def insertion_sort(arr: list[int]) -> list[int]: # 배열 전체를 반복하면서 for ..