삽입 정렬 알고리즘 (Insert Sort)

삽입 정렬 알고리즘(Insert Sort Algorithm)

위치 교환이 발생한 것을 대상으로 주변의 것과 비교하여 위치를 교환하는 알고리즘

1. 사이즈 7의 정렬할 배열을 가정합니다. (size=7)
   

2. 앞에서부터 인접한 두 개의 크기를 비교하여 작은 것이 앞을 가도록 위치를 교환합니다.
   

3. 위치를 교환한 것 대상으로 주변과 비교합니다. 위치 교환이 없다면 그 다음 데이터를 비교합니다.

4. 214와 110을 비교하여 위치를 교환합니다.
   

5. 위치를 교환한 110과 주변을 비교하여 위치를 교환합니다.
   

6. 다음 데이터를 비교하여 259와 316을 비교하여 위치를 교환합니다.
   

7. 정렬완료
   

삽입 정렬 알고리즘 구현

# PYthon 3.8

def insert_sort(x):
    for i in range(1, len(x)):
        value = x[i]
        idx = i
        while idx > 0 and x[idx-1] > value:
            x[idx] = x[idx-1]
            idx -= 1
        x[idx] = value
    return x

github : https://github.com/honeybeeveloper/algorithm/blob/develop/insert-sort.py
참고 : 책 <그림으로 정리한 알고리즘과 자료구조>