삽입정렬(Insertion sort)

이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입한다.

아래 그림을 보면 이미 정렬되어 있는 부분이 어느정도 있다고 가정하자.

이후 sort된 부분과 X를 비교한다. 

그리고 X가 큰 값이 나오기 전의 위치에 값을 삽입한다.

아래는 python 로 작성한 코드이다.

def insertion_sort(unsort_data):
    sort_data = []
    for unsorted_index in range(len(unsort_data)):
        position = -1
        pivot = unsort_data[unsorted_index]
 
        for sorted_index in range(len(sort_data)):
            if(sort_data[sorted_index] > pivot):
                position = sorted_index
                break
 
        if(position == -1):
            position = len(sort_data)
 
        sort_data.insert(position, pivot)
        ##print("sorting..",sort_data)
 
    return sort_data
 
if __name__ == "__main__":
    ll = [31, 25, 121, 22, 11]
    print(insertion_sort(ll))