알고리즘_삽입 정렬

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입한다. (제자리 정렬)

 

삽입 정렬의 시간 복잡도는 보통 O(N^2)이지만

데이터가 정렬되어 있는 경우 매우 빠르게 동작한다. O(N)

 

장점

안정적이다

배열이 정렬 되어있는 경우 매우 효율적이다.

단점

그냥 비효율적이다

배열이 길면 느림;;

arr = [7,4,6,6,8,9,2,5]


for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j] < arr[j-1]:
            arr[j], arr[j - 1] = arr[j - 1], arr[j] 
        else:
            break