삽입 정렬(insertion sort)

삽입 정렬

삽입 정렬은 key값을 배열의 알맞는 위치로 삽입하여 정렬하는 방식입니다.

시간복잡도

- o(n^2)

계획세우기

1. 시작 index는 1부터 시작하여 앞 index들과 비교를한다.

2. key값이 앞 index들보다 크면 그대로 고정

3. key값이 작으면 array의 value값을 뒤로 보낸다.

4. 저장된 key값을 맞는 위치에 넣는다.

그림으로 이해하기

파이썬으로 구현

arr = [8, 5, 6, 2, 4]

def insertion_sort(list):
	n = len(arr)
    for i in range(1, n):
    	key_value = list[i]
        # key값 뒤값 index
        j = i -1 
        while j >= 0 and list[j] > key_value :
        	list[j+1] = list[j]
        	j -= 1
        list[j+1] = key_value
        
	return list

print(insertion_sort(arr))

정리

기본 정렬이지만 시간 복잡도가 오래걸리기 때문에 역시 개념, 구현 위주로 이해하고 넘어가면 된다.