삽입 정렬 (Insertion Sort)
목차
두 번째 인덱스부터 시작하여 작은 값을 앞으로 보내는 알고리즘. 해당 값보다 작은 값을 만날 때까지 이동한다.
구현
def insertion_sort(data):
for index in range(1, len(data)):
for insertion in range(index, 0, -1):
if data[insertion] < data[insertion - 1]:
data[insertion], data[insertion - 1] = data[insertion - 1], data[insertion]
else:
break
return data시간 복잡도
| 경우 | 복잡도 |
|---|---|
| 일반 | O(n²) |
| 최악 | n*(n-1)/2 |
| 완전 정렬 상태 | O(n) |