Insertion Sort

두번째 자료부터 시작, 그 앞 자료들과 비교하여 삽입 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘

def insertionSort(arr):
	for i in range(1, len(arr)):
    	key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
        	arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

시간복잡도

최선: O(n), 평균/최악: O(n^2)

공간복잡도

O(n)

장점

• 단순
• 이미 정렬되어 있을 경우 효율적
• 제자리 정렬
• 안정 정렬

단점

• 비효율적
• 배열의 길이가 길어질수록 비효율적

References

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%82%BD%EC%9E%85%20%EC%A0%95%EB%A0%AC%20(Insertion%20Sort).md#%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC-insertion-sort

https://www.geeksforgeeks.org/insertion-sort/