[python]삽입 정렬(insertion sort) 알고리즘

삽입 정렬

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

k번째 반복 후의 결과 배열은, 앞쪽 k+1 항목이 정렬된 상태

 

설명

5개의 숫자가 들어있는 리스트가 있다.

 

두번째의 값을 key로 갖는다.

해당 그림에서는 8이 key가 된다.

 

key값을 기준으로 그 앞의 값들과 비교한다. 즉, 왼쪽의 값들과 비교하며 자신의 자리를 찾는다.

key인 8의 값을 그 앞에 위치한 6의 값과 비교한다.

8이 6보다 크기 때문에 자리를 바꾸지 않는다.

 

그 다음 key의 값은 세번째인 3이 된다.

3보다 앞에 위치한 8과 먼저 비교한다. 3이 더 작으므로 위치를 바꿔준다.

그 다음 key인 3보다 앞에 위치한 6과 비교한다. 3이 더 작으므로 위치를 바꿔준다.

 

다음 key의 값은 네번째에 위치한 9가 된다.

이 또한 마찬가지로 차례대로 앞의 값과 비교를 하며 정렬해준다.

앞에 값들이 9보다 모두 작으므로 자리 변동이 없다.

 

마지막 다섯번째에 위치한 4가 다음 key 값이 된다.

마찬가지로 차례대로 앞의 값들과 비교하여 정렬한다.

이 모든 과정을 마치고 나면 오름차순으로 정렬된 리스트를 확인할 수 있다.

 

python 구현

lst = [6, 8, 3, 9, 4, 2]
print(lst)

for i in range(1, len(lst)):
    for j in range(i, 0, -1): 
        if lst[i] < lst[j-1]:
            tmp = lst[j-1]
            lst[j-1] = lst[i]
            lst[i] = tmp
            i -= 1

print(lst)

내가 맨 처음에 작성한 코드이다.

출력에는 문제가 없다.

 

하지만 좀 더 코드를 다듬어 줄 수 있었다.

(인프런 강의 참조하여 수정)

lst = [6, 8, 3, 9, 4, 2]
print(lst)

for i in range(1, len(lst)):
    while i > 0 and lst[i-1] > lst[i]:
        lst[i-1], lst[i] = lst[i], lst[i-1]
        i -= 1

print(lst)

 

위키백과에 나와있는 코드

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

 

시간복잡도

최선의 경우: O(n)

최악의 경우: O(n^2)

 

 

 

출처

https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC

https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html

https://rninche01.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC