[Python]Insertion Sorting

 

삽입정렬은 자기 위치를 기준으로 앞 인덱스의 값과 비교해서 크기가 작다면 앞에다가 삽입(swap)하는 것이다.

장점은 N의 크기가 작을때 효과적이라는 것

단점은 성능이 좋지 않다는 것이다. 평균 시간복잡도 O(N^2)

 

정리

• 현재 인덱스를 정렬될 리스트의 끝으로 보고 전체 순회
• 현재 인덱스 값을 앞 인덱스 값과 비교/스와핑 후 인덱스 업데이트 반복
• 업데이트 반복 조건은 idx > 0 and arr[idx-1] > arr[idx

def insertion_sort(a):
    n = len(a)
    for i in range(n):
        for j in range(i-1, -1, -1):
            if a[i] < a[j]:
                a[i], a[j] = a[j], a[i]
                i = j