[알고리즘 이론] 삽입 정렬 (Insertion Sort)

• 삽입 정렬: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 두 번째 인덱스부터 시작함

출처: https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

 

""" 삽입 정렬 구현 코드 """

def insertion_sort(data):
	for i in range(len(data) - 1):
		for j in range(i+1, 0, -1):
			if data[j] < data[j-1]:
				data[j], data[j-1] = data[j-1], data[j]
			else:
				break
	return data

 

- 반복문이 두 개 이므로 시간 복잡도 : O(n^2)