[python]삽입정렬

삽입정렬은 특별한 경우, 즉 정렬되어있는 리스트가 입력값으로 전달되는 경우 O(n)이고, 일반적으로는 선택정렬과 같이 O(n^2)이다.

 

def ins_sort(a): #오름차순
    n=len(a)
    for i in range(1, n): #idx:1~n-1(끝)
        key=a[i]
        j=i-1
        while j>=0 and a[j]>key:
            a[j+1]=a[j]
            j-=1
            print(a, key)
        a[j+1]=key
        
 
d=[2, 4, 5, 1, 3]
ins_sort(d)
print(d)
        
 

key가 4와 5일 경우 리스트의 형태는 변하지 않는다. 하지만 key가 1, 3일 경우에는 상황이 달라진다.