알고리즘 - 단순 삽입 정렬

4

2

1

7

9

6

 

오름차순으로 정렬을 할 때, 위 배열에서 현재 원소 2를 보고있다면 2는 4보다 앞에 있어야 하기 때문에

 

2

4

1

7

9

6

 

이렇게 앞으로 한 칸 옮겨주면 됩니다.

원소 1을 올기면 4와 2를 지나쳐 맨 앞으로 옮겨줍니다.

 

1

2

4

7

9

6

 

이렇게 가장 작은 원소를 정하는 것이 아닌, 현재 보고 있는 원소를 알맞은 위치로 옮기는 것을

단순 삽입 정렬이라고 합니다.

 

---

def insertion_sort(a) -> None:
    n = len(a)
    for i in range(1, n):
        j = i
        tmp = a[i]
        while j > 0 and a[j - 1] > tmp:
            a[j] = a[j-1]
            j -= 1
        a[j] = tmp


print('단순 삽입 정렬')
num = int(input('원소 수 입력: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

print(''.join(str(x)))
insertion_sort(x)
print(''.join(str(x)))

 

insertion_sort 함수를 보겠습니다.

일단 for문이 1부터 시작하는 이유는 두 번째 원소부터 정렬을 시작하기 때문입니다.

j는 인덱스 값이고 tmp는 정렬시킬 원소입니다.

 

while문은 앞 인덱스와 비교해서 현재 정렬하려는 원소 값이 더 작으면 계속 바꿔주는 것입니다.

while문이 종료되면 a[j]에 삽입할 tmp를 넣어줍니다.