[정렬] 삽입 정렬(Insertion Sort)

- 정렬되어 있는 데이터들을 비교하며 적절한 위치에 삽입
- 데이터가 거의 정렬 되어 있을 때, 효율적

 

시간 복잡도 : O(N^2) 최선의 경우 O(N)
공간 복잡도: O(N)

 

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

for i in range(1, len(array)): #첫 번째 데이터는 정렬되어 있다고 판단
    for j in range(i, 0, -1):
    	if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break

 

---

정렬 전체가긔

이것이 코딩 테스트다 - 나동빈
정리하긔