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

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

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,
자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

최악의 경우 시간복잡도 : (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2= O(n&2) (최악의 경우)

최선의 경우 시간복잡도 : O(n) (정렬이 모두 되어있는 경우에는 한 번 씩만 비교하면 되기 때문)

 

[예시]

각 회전 마다 연두색 밑줄이 되어 있는 부분이 이미 정렬된 배열 부분!

 

[ 코드 ]

def insertion_sort(arr):
    for end in range(1, len(arr)):
        for i in range(end, 0, -1):
            if arr[i - 1] > arr[i]:
                arr[i - 1], arr[i] = arr[i], arr[i - 1]