삽입 정렬 - 파이썬

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

구현 아이디어

1. 이미 정렬된 list에 새로운 원소를 추가하여 정렬하는 알고리즘
2. 타겟 원소 이전의 원소들과 값을 비교하여 자리를 바꾼다

def InsertionSort(a,n):
	for i in range(1,n):
    	for j in range(i,0,-1):
        	if a[j] < a[j-1]:
            	a[j], a[j-1] = a[j-1], a[j]
        	else:
            	break
    return a

전체 원소를 비교하는 횟수 : $1 + 2 + ... + n-1$
시간복잡도 : $O(n^2)$
*정렬되어있는 경우에는 $O(n)$시간도 가능하나 평균적으로 $O(n^2)$의 시간복잡도를 가짐