삽입정렬

삽입정렬은 정렬되어 있는 숫자들에 또 다른 숫자를 넣어 하나씩 탐색한 후 맞는 자리에 끼워 넣는 정렬방법이다.

이도 똑같이 for문을 두 번 사용하여 O(N^2)만큼의 시간 복잡도가 걸리지만, 비교하는 값이 정렬이 되어 있는 상태라면 break문을 사용하여 for문을 빠져나오므로 정렬이 어느 정도 되어 있는 상태에서는 선택정렬과 버블정렬보다 좀 더 효율적이다.

input = [4, 6, 2, 9, 1]
def insertion_sort(array):
    n = len(array)
    for i in range(1,n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1],array[i - j] = array[i - j],array[i - j - 1]
            else:
                break
    return array

result = insertion_sort(input)
print(result)

i 값이 1일 때 부터 for문을 도는 이유는 값이 하나만 있을 때에는 이미 정렬이 되어 있다고 보기 때문에 굳이 for문을 돌지 않아도 되기 때문이다. i를 1부터 시작 해 배열의 끝까지 돌면서 두 번 째 for문은 i만큼 돌아준다. (있는 값들만 비교하면 되기 때문에) 그 후 새로운 값을 넣을 때 값들을 뒤에서 부터 비교하면서 만약 정렬이 되어있지 않다면 정렬 해 주고, 정렬이 되어 있다면, break문을 써서 for문을 빠져나온다. 

이 과정들을 모두 반복하여 정렬이 끝난다면 정렬 된 배열을 반환한다.