삽입 정렬이란

두번째 자료부터 시작, 그 앞 자료들과 비교하여 삽입 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘 def insertionSort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j+1] = arr[j] j -= 1 arr[j+1] = key 시간복잡도 최선: O(n), 평균/최악: O(n^2) 공간복잡도 O(n) 장점 단순 이미 정렬되어 있을 경우 효율적 제자리 정렬 안정 정렬 단점 비효율적 배열의 길이가 길어질수록 비효율적 References https://github.com/GimunLee/tech-refrigerator/blob/master..