[알고리즘] 삽입정렬 (Insertion Sort)

책에서는 간단한 알고리즘 이라고 소개하고 있지만,
삽입정렬의 알고리즘은 초보자에게는 어려울 것이다.
배열수(N)이 라고 하면 복잡도는 O(N^2)이 되어 최악의 알고리즘이라고 할 수 있지만,
이미 어느 정도 정렬되어 있다고 가정하면 그렇게 나쁜 알고리즘은 아니다 ㅋㅋ

arr = [8, 5, 4, 3, 2, 1] 이란 정수 배열이 있다고 가정하자.
이 알고리즘의 핵심은 i번째 배열의 값을 저장 후 0~(i-1) 배열의 값과 비교하는 과정이 있는데
0~(i-1)의 배열은 정렬이 되어 있다. i의 값을 1부터 N-1 (N은 배열수)까지 순회하면서
다음과 같은 작업을 진행한다.

arr = [8, 5, 4, 3, 2, 1] 
print(arr)
def insert_sort(arr):
    for i in range(1, len(arr)):
        v = arr[i] # 선택값
        j = i - 1 
        while j >= 0 and arr[j] > v:
            arr[j+1] = arr[j] # 선택값 보다 크면
            j -= 1
        arr[j+1] = v # 선택값 보다 작거나 같으면 
        print(arr)
 
#[8, 5, 4, 3, 2, 1]
#[5, 8, 4, 3, 2, 1]
#[4, 5, 8, 3, 2, 1]
#[3, 4, 5, 8, 2, 1]
#[2, 3, 4, 5, 8, 1]
#[1, 2, 3, 4, 5, 8]

# 아무 생각 없이 끄적임 ㅋㅋ
def insert_sort(arr):
    print(arr)
    for i in range(1, len(arr)):
        j = i
        while j>0:
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
            j -= 1
        print(arr)