알고리즘 개념 6. 삽입정렬 (Insertion sort)

 

개념?

- 자신보다 그 앞의 원소가 큰지, 작은지를 판단하여 자신의 위치를 찾아 삽입하는 정렬

- 오름차순,내림차순

- 자기자신이 n번째에 있으면 첫번째원소부터 n까지 비교

 

시간복잡도: O(n^2)

-특정한 경우에 빠른 속도가 나지만(정렬이 되어있다고 가정), 

 배열이 길어지면 효율이 떨어진다. 

 

예시

9 4 6 2 1 5

 

단계별 출력

9

4 9

4 6 9 

2 4 6 9 

1 2 4 6 9

1 2 4 5 6 9

 

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

 

python 코드 포인트 

arr[i - 1], arr[i] = arr[i], arr[i - 1]