삽입 정렬 (Insertion Sort)

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

시간 복잡도

Best - O(N)

Average - O(N^2)

Worst - O(N^2)

설명

삽입 정렬은 길이가 n인 배열에서 인덱스가 1번인 요소(두 번째 요소)부터 시작한다.

 

배열에서 요소를 선택해서 이전 인덱스의 요소들과 비교하여 적절한 위치에 삽입한다.

 

이를 n - 1번 반복하면 오름차순 또는 내림차순으로 정렬을 완성할 수 있다.

구현(파이썬)

arr = [6, 5, 3, 1, 8, 7, 2, 4]

for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        # 오름차순 기준, 내림차순은 부호를 반대로
        if arr[j - 1] > arr[j]:
            arr[j - 1], arr[j] = arr[j], arr[j - 1]
        else:
            break