개념

선택정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.

1. 정렬 대상이 될 원소를 두 부분으로 나눔
   • 앞은 ‘이미 정렬이 된 부분’ → 정렬이 끝난 것 x 앞 부분에 있는 원소는 오름차순을 만족함 o
   • 뒤는 ‘정렬 할 부분’
2. 매번 정렬 할 부분(뒷 부분)의 가장 첫 번째 원소를 정렬이 된 부분(앞 부분)에 삽입한다.
3. 삽입은 정렬된 부분의 가장 큰 원소(앞 부분의 가장 오른쪽 원소)부터 쪽으로 비교해 나가면서 진행한다.

시간복잡도

• 최적의 경우: 이미 오름차순으로 정렬되어 있을 때
  • 정렬된 부분에 원소를 넣을 때마다, 비교를 한 번만 하면 된다.
  • 총 n-1번 ⇒ $O(N)$
• 최악의 경우: 역순으로 정렬된 수들을 정렬할 때
  • i번째 위치의 원소를 정렬된 부분에 추가할 때 (즉, 이미 정렬된 앞 부분에 i-1개의 원소가 있을 때) i-1개의 원소와 모두 비교한다.
  • i=2, 3, …, n이므로 $1+2+..+n-1 = n(n-1)$ ⇒ $O(N^2)$

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 $O(n)$이다.

예시코드

import random

def insert_sort(A):
    result=[]
    while(A):
        num=A.pop(0) #가장 앞을 뽑아서
        result.append(num) #result의 가장 뒤에 넣기
        
        for i in range(len(result)-1,0,-1): #정렬된 곳 가장 뒤부터 가장 앞까지
            if(result[i]<result[i-1]): #num이 바로 앞의 수보다 클 때까지 교환해가면서 반복
                result[i],result[i-1]=result[i-1],result[i]
            else:break
    return result
        
    
if __name__=="__main__":
    num_list=list(range(1,21))
    random.shuffle(num_list)
    print("정렬 전 :",num_list)
    print("정렬 후 :",insert_sort(num_list))

정렬 전 : [12, 6, 17, 9, 10, 20, 14, 18, 2, 3, 11, 15, 19, 4, 5, 16, 8, 13, 7, 1]
정렬 후 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

장점