삽입 정렬 알고리즘

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다.

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작합니다.

동작 예시

[Step 0] 첫 번째 데이터 7은 그 자체로 정렬이 되어있다고 판단하고, 두 번째 데이터인 5가 어떤 위치로 들어갈지 판단합니다. 7의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재합니다.

[Step 1] 이어서 9가 어떤 위치로 들어갈지 판단합니다.

[Step 2] 이어서 0이 어떤 위치로 들어갈지 판단합니다.

[Step 3] 이어서 3이 어떤 위치로 들어갈지 판단합니다.

이러한 과정을 반복하면 다음과 같이 정렬이 완료됩니다.

소스코드

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

for i in range(1,len(array)):
	for j in range(i,0,-1):	# 인덱스 i부터 1까지 1씩 감소하며 반복
    	if array[j] < array[j-1]:	# 한 칸 씩 왼쪽으로 이동
        	array[j], array[j-1] = array[j-1], array[j]
        else:	# 자기보다 작은 데이터를 만나면 break
        	break
print(array)

# 실행 결과 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용됩니다.

삽입 정렬은 현재 리스트 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작합니다.
최선의 경우 O(N)의 시간복잡도를 가집니다.