삽입정렬 (Insertion Sort)

📌 삽입정렬 (Insertion Sort)

배열에서 현재 자신의 위치보다 앞에 이미 정렬된 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 방법이다.

 

👉 과정

Loop 1

[5, 3, 8, 1, 2, 7]
current_idx: 1
current_val: 3
arr[current_idx - 1]: 5

인덱스 1번에 5삽입

[5, 5, 8, 1, 2, 7]
current_idx: 0
current_val: 3
arr[current_idx - 1]: 5

current_idx가 0이 됐기 때문에 while문에 걸리지 않고 인덱스 0에 current_val을 삽입

[3, 5, 8, 1, 2, 7]
current_idx: 0
current_val: 3
arr[current_idx - 1]: 5

 

Loop 2

[3, 5, 8, 1, 2, 7]
current_idx: 2
current_val: 8
arr[current_idx - 1]: 5

3, 5, 8은 이미 정렬되어 있으므로 그냥 넘어간다.

 

Loop 3

[3, 5, 8, 1, 2, 7]
current_idx: 3
current_val: 1
arr[current_idx - 1]: 8

while문 조건에 걸린다.

8이 1보다 크므로 1의 자리인 인덱스 3에 8을 삽입하고 current_idx를 1 감소

[3, 5, 8, 8, 2, 7]
current_idx: 2
current_val: 1
arr[current_idx - 1]: 5

여기서도 while문 조건에 걸린다.

인덱스 2에 5를 삽입하고 current_idx는 1 감소

[3, 5, 5, 8, 2, 7]
current_idx: 1
current_val: 1
arr[current_idx - 1]: 3

while문 조건에 걸리고 인덱스 1에 3을 삽입하고 current_idx는 1 감소

[3, 3, 5, 8, 2, 7]
current_idx: 0
current_val: 1
arr[current_idx - 1]: 5

while문 조건에 걸리지 않아 인덱스 1에 current_val인 1을 삽입

[1, 3, 5, 8, 2, 7]
current_idx: 0
current_val: 1
arr[current_idx - 1]: 5

 

Loop 4

[1, 3, 5, 8, 2, 7]
current_idx: 4
current_val: 2
arr[current_idx - 1]: 8

8과 2를 비교

8이 더 크므로 2번 자리인 인덱스 4에 8을 삽입

[1, 3, 5, 8, 8, 7]
current_idx: 3
current_val: 2
arr[current_idx - 1]: 8

current_val인 2와 5를 비교

5가 더 크기 때문에 인덱스 3에 5를 삽입

[1, 3, 5, 5, 8, 7]
current_idx: 2
current_val: 2
arr[current_idx - 1]: 5

current_val인 2와 3을 비교

3이 더 크기 때문에 인덱스 2에 3을 삽입

[1, 3, 3, 5, 8, 7]
current_idx: 1
current_val: 2
arr[current_idx - 1]: 1

current_val인 2가 1보다는 크기 때문에 루프는 끝이나고 인덱스 1에 2를 삽입

[1, 2, 3, 5, 8, 7]
current_idx: 1
current_val: 2
arr[current_idx - 1]: 1

루프 종료

 

Loop 5

[1, 2, 3, 5, 8, 7]
current_idx: 5
current_val: 7
arr[current_idx - 1]: 8

8과 7을 비교

8이 7보다 크므로 7의 자리인 인덱스 5에 8을 삽입

[1, 2, 3, 5, 8, 8]
current_idx: 4
current_val: 7
arr[current_idx - 1]: 5

current_val인 7과 5를 비교

7이 더 크기 때문에 while문 조건에 만족하지 않는다.

루프를 끝냄

[1, 2, 3, 5, 7, 8]
current_idx: 4
current_val: 7
arr[current_idx - 1]: 5

인덱스 4에 7을 삽입

for loop 종료하면서 정렬 끝

 

👉 구현

def insertion_sort(arr):
    for i in range(1, len(arr)):
        current_val = arr[i]
        current_idx = i

        while current_idx > 0 and current_val < arr[current_idx - 1]:
            arr[current_idx] = arr[current_idx - 1]
            current_idx -= 1

        arr[current_idx] = current_val

    return arr