[Algo] 삽입 정렬

1. 동작 원리

[ 4, 2, 7, 1, 3 ] 데이터를 정렬해보자

a. 인덱스 1부터 끝까지 반복할 것이다.

b. 2와 4를 비교
- 2가 작기때문에 4 앞에위치 [ 2, 4, 7, 1, 3 ]

c. 7과 4를 비교
- 4가 작기 때문에 그대로 [ 2, 4, 7, 1, 3 ]

d. 1과 7을 비교
- 1이 작기 때문에 7 앞으로 이동 [ 2, 4, 1, 7, 3]
- 1이 4보다 작기 때문에 4 앞으로 이동 [ 2, 1, 4, 7, 3 ]
- 1이 2보다 작기 때문에 2 앞으로 이동 [ 1, 2, 4, 7, 3 ]

e. 3과 7을 비교
- 3이 작기 때문에 7 앞으로 이동 [ 1, 2, 4, 3, 7 ]
- 3이 4보다 작기 때문에 4 앞으로 이동 [ 1, 2, 3, 4, 7 ]

f. 정렬 할 것이 없기 때문에 종료

즉, 인덱스 1부터 끝까지 반복하는데,
각 인덱스보다 앞에있는 값들을 전부 비교해서 정렬한다.

2. Code

import time
import numpy as np


def insertion_sort(data):

  for idx in range(1, len(data)):

    tmp = data[idx]

    position = idx - 1

    while position >= 0:

      if tmp < data[position]:
        data[position + 1] = data[position]
        position -= 1
        
      else:
        
        break

    data[position + 1] = tmp

  return data

# 1~20 중 중복 없이 10개 숫자 추출
t1 = time.time()
data = np.random.choice(range(1, 20), 10, replace=False)

result = insertion_sort(data)

t2 = time.time()

print(result)

print(f"실행시간 : {t2 - t1:.8f}")