삽입 정렬을 만들어보자

def insertsort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        temp = i
        while 0 < temp and arr[temp - 1] > key:
            arr[temp] = arr[temp - 1]
            temp -= 1
        arr[temp] = key
    return arr
print(insertsort([3, 2, 1]))

 

i	key	temp	arr[temp]	arr[temp-1]	while문	temp 변경	arr
1	2	1	2	1	True	1 >> 0	[3, 3, 1]
1	2	0			False		[2, 3, 1]
2	1	2	1	3	True	2 >> 1	[2, 3, 3]
2	1	1	3	2	True	1 >> 0	[2, 2, 3]
2	1	0			False		[1, 2, 3]
for문을 모두 돌았기 때문에 현재 arr인 [1, 2, 3]을 리턴한다.

 

1. 배열의 2번째 요소부터 배열의 끝까지 반복한다.

2. key값에 현재 선택된 요소의 값을 저장, 현재 배열의 index를 temp에 저장한다.

3. while문을 돌며 가장 작은 요소를 찾는다.

(while문은 temp값이 0보다 클 때, arr[temp - 1]값이 key값보다 작을 때 동작한다.)

4. while문 조건에 성립한다면 arr[temp]값에 arr[temp-1] 값을 삽입하고 temp값을 -1한다.

5. while문 조건에 성립하지 않는다면 key값의 위치를 찾은 것이므로 현재 temp위치에 key값을 삽입한다.