정렬 2(삽입정렬)

출처 : (이코테 2021 강의 몰아보기) 4. 정렬 알고리즘
https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

삽입정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택 정렬에 비해 일반적으로 더 효율적
첫 번째 데이터는 그 자체로 정렬이 되어 있다고 가정
삽입 정렬의 시간 복잡도는 O(N^2)
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작 => 최선의 경우 O(N)의 시간복잡도

코드

#삽입정렬
array=[7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(array)):
    for j in range(i,0,-1):
        if array[j]<array[j-1]:
            array[j],array[j-1]=array[j-1],array[j]
        else:
            break
print(array)