삽입정렬(Insertion sort)

1. 삽입정렬이란?

두번째 인덱스부터 시작하여 해당 인덱스 앞에 있는 데이터부터 비교해서 그 값이 더 크다면 값을 서로 교환.

 

2. 구현코드

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

 

3. 시간복잡도

• 최악의 경우: O(N^2)
• 완전 정렬이 된 경우: O(N)