Insertion sort - 삽입 정렬

정렬 대상의 N번째 원소를 적절한 위치에 삽입한다.

• 정렬 대상의 맨 처음 원소부터 하나씩 적절한 위치에 삽입한다.
• 구체적으로, N 번째 원소를 1부터 N-1번째의 적절한 위치에 삽입한다.

import sys
from random import shuffle

input = sys.stdin.readline

N = int(input())
lst = [_ for _ in range(1, N + 1)]
shuffle(lst)

print("정렬 전 : {}".format(lst))

# insert sort
for i in range(1, N):
    # i 번째 원소의 적절한 위치를 찾는다.
    j = i 
    
    # 위치를 찾을 때까지 반복한다.
    while lst[j] < lst[j - 1] and j >= 1:
        lst[j], lst[j - 1] = lst[j - 1], lst[j]
        j -= 1

print("정렬 후 : {}".format(lst))