10000COW

삽입 정렬 - 이미 정렬된 부분은 항상 정렬되어 있다. - 처음에는 정렬된 부분에 원소가 1개 - 매번, 정렬할 부분의 원소 1개를 이미 정렬된 부분으로 옮긴다. 시간 복잡도 Θ(n^2) - 가장 좋을 때: 이미 오름차순으로 정렬되어 있을 때 -> 총 n-1 번 = Θ(n) - 최악의 경우: 역순으로 정렬되어 있을 때 i번째 위치의 원소를 정렬된 부분에 추가할 때, i-1 개의 원소와 모두 비교해야한다. i = 2,3, ..., n일 때 각각 비교해야할 개수는 1+ 2+ ... + n-1 = n(n-1)/2 = Θ(n^2) 삽입 정렬 Python 코드 def insertionSort(): nums = list(map(int, input().split(' '))) for i in range(1, len(n..