정렬 - 삽입 정렬(insertion sort)

1. 삽입 정렬(insertion sort) 란?

🖐 두 번째 인덱스부터 시작하여 앞의 수와 비교하는 알고리즘

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

2. 단순하게 생각하기

👉 뒷 수와 앞의 수를 비교 !

data = [4, 1]
for idx in range(1,len(data)):
    if data[idx] > data[idx -1]:  # 뒷 수와 앞의 수를 비교
        data[idx], data[idx-1] = data[idx-1], data[idx]
        
# 출력 결과: [1, 4]

 

3. 알고리즘 구현

✍ 두번째 수부터 시작 

✍ 뒤에서 앞으로 !

def insertion_sort(data):
    for t in range(len(data)-1):
        for idx in range(t + 1, 0, -1):  #뒷 수와 앞의 수를 비교
            if data[idx] < data[idx-1]:  # 앞의 수가 뒷 수보다 크면
                data[idx], data[idx-1] = data[idx-1], data[idx]  # 스왑 !
            else: 
                break
    return data
    
insertion_sort([9,7,5,3,1])
# 출력 결과: [1,3,5,7,9]

 

4. 복잡도

👉 반복문이 두 개  O(n**2)

👉 완전 정렬되어 있는 상태라면 최선은 O(n) /  최악의 경우 n*(n-1) / 2