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

삽입 정렬 (Insertion Sort) 이란?
- 두 번째 원소부터 자신의 앞에 먼저 정렬된 리스트 안에서 자신의 위치를 찾아 삽입하여 정렬하는 알고리즘
  - 비교 정렬에 속함
- 삽입 정렬 특징
  - 최적의 상태에서 굉장히 빠른 성능을 가진 알고리즘 – O(N)
  - 최악의 경우 O(N²) 로 성능의 편차가 심함
  - 구현이 쉬움
- 삽입 정렬 알고리즘 시간 복잡도
  - 최악, 평균 – O(N²)
  - 최선 – O(N)
  - 참고 – 각 정렬 알고리즘의 시간복잡도

예제 – 오름차순

# Python Code

arr = [3,1,6,0,1,9,4]
N = len(arr)

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

print(arr)
# [0, 1, 1, 3, 4, 6, 9]