[Python] 정렬 알고리즘(3)-삽입 정렬

• 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.
• 선택정렬에 비해 구현 난이도가 높은 편이지만 실행시간 측면에서 더 효율적으로 동작합니다.

삽입 정렬 소스코드 (Python)

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

for i in range(1, len(arr)): 
	for j in range(i, 0, -1): #(start, end, step) 
		if arr[j] < arr[j -1]: # 한 칸씩 왼쪽으로 이동 
			arr[j], arr[j -1] = arr[j -1], arr[j] 
		else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 
			break

삽입 정렬의 시간 복잡도

• 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됩니다.
• 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
  • 최선의 경우 O(N)의 시간 복잡도를 가집니다.
  • 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 어떻게 될까요?