Sorting algorithm(정렬 알고리즘) 2탄 - Insertion sort(삽입 정렬)

 

2. Insertion sort  삽입 정렬

- 왼쪽에서 2번째 수와 첫번째 수를 비교해서 작은 걸 첫번째에 위치시킴. (둘을 swap.)

→ 다음 수 즉, 왼쪽에서 3번째 수와 이미 정렬한 두 수를 비교하여 3번째 수의 위치를 찾아서 정렬시킴.

→ 같은 방식으로 4번째 수와 1~3번째 수를 비교해서 정렬시킴.

→ 계속 반복.

 

 

왼쪽에서 첫번째 수(70)는 이미 정렬된 것으로 간주.

왼쪽에서 두번째 수 30 < 70 

→ 30의 위치는 70의 앞이여야 하므로 30과 70 swap.

 

 

30, 70은 정렬됨.

100 vs 70 → 70 < 100 이므로 100은 70 다음이어야 함. 즉, swap할 필요 없음.

 

 

60 vs 100  →  60 < 100 이므로 100과 60 swap.

60 vs 70  →  60 < 70 이므로 100과 60 swap.

60 vs 30  →  60 > 30 이므로 swap하지 않음.

 

 

5 vs 100  →  5 < 100 이므로 100과 5 swap.

5 vs 70  →  5 < 70 이므로 70과 5 swap.

5 vs 60  →  5 < 60 이므로 60과 5 swap.

5 vs 30  →  5 < 30 이므로 30과 5 swap. 끝!

 

 

정렬 완료!!

 

 

 

# 버전1
from typing import List
def insertion(L: List) -> List:
    for i in range(1,len(L)):
        idx = i
        for z in range(i-1, -1 ,-1):
            if L[z] > L[idx]:
                L[z], L[idx] = L[idx], L[z]
                idx = z
            else:
                break

    return L

insertion([500, 20, 7, 100, 100, 17, 34, 17])
# [7, 17, 17, 20, 34, 100, 100, 500]

 

 

# 위 코드(버전1)보다 더 깔끔한 느낌의 코드.
from typing import List
def insertion(L: List) -> List:
    for i in range(1,len(L)):
        for z in range(i, 0 ,-1):
            if L[z-1] > L[z]:
                L[z], L[z-1] = L[z-1], L[z]
            else:
                break

    return L

insertion([500, 20, 7, 100, 100, 17, 34, 17])
# [7, 17, 17, 20, 34, 100, 100, 500]