삽입 정렬 알고리즘

arr[] = 5 | 4 | 6 | 8 | 2 | 3 | 1 | 7 | 9 | 0

삽입 정렬로 위 배열을 오름차순으로 정렬해보자.

 

삽입 정렬은 두번째 배열을 먼저 선택해 해당 인덱스의 앞값들과 비교해 삽입하는 방식이다.

 

먼저 arr[1]=4와 앞의 값 arr[0]=5와 비교한다. arr[1] < arr[0]이므로 삽입 한다.

 

arr[] = 4 | 5 | 6 | 8 | 2 | 3 | 1 | 7 | 9 | 0

 

다음은 arr[2]=6과 앞의 값들을 비교하는데 [1],[0] 모두 작으므로 비교할게 없다. arr[3]=8또한 비교할게 없다.

 

arr[4]=2와 8를 먼저 비교, arr[4] < arr[3]이므로 swap한다.

다음 값 arr[2]=6과 arr[3]=2비교, 작으므로 swap. 

다음 값 arr[1]=5와 arr[2]=2비교, 작으므로 swap.

다음 값 arr[0]=4와 arr[1]=2비교, 작으므로 swap.

arr[0]=2가 된다.

 

arr[] = 2 | 4 | 5 | 6 | 8 | 3 | 1 | 7 | 9 | 0

 

arr[5]=3과 8,6,5,4와 비교로 swap, arr[0]=2와 비교했을 때 크므로 멈춘다.

 

arr[] = 2 | 3 | 4 | 5 | 6 | 8 | 1 | 7 | 9 | 0

 

arr[6]=1과 8,6,5,4,3,2를 비교 후 swap.

 

arr[] =  1 | 2 | 3 | 4 | 5 | 6 | 8 | 7 | 9 | 0

 

arr[7]=7과 8을 비교 후 swap. 6보다 크므로 멈춘다.

 

arr[] =  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

 

arr[7]=8과 9을 비교하는데 크므로 변화 없음.

 

arr[] =  1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

 

마지막 0은 9,8,7,6,5,4,3,2,1과 비교 후 swap하여 마무리 한다.

 

arr[] = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

 

arr = [5, 4, 6, 8, 2, 3, 1, 7, 9, 0]

def ins_sort(arr):
    length= len(arr)
    for i in range(1,length):
        for j in range(i,0,-1):
            if arr[j] < arr[j-1]:
                arr[j],arr[j-1] = arr[j-1],arr[j]

print("before : ",arr)
ins_sort(arr)
print("after : ",arr)