[자료구조] 삽입 정렬(Insertion sort) - python

파이썬 자료구조와 알고리즘 - 한빛아카데미

파이썬 자료구조와 알고리즘 교재 공부한 내용을 적어보았습니다.

---

삽입 정렬(Insertion sort)이란 기존 데이터 중에서 자신의 위치를 찾아 데이터를 삽입하여 정렬하는 방식입니다.

 

기존의 정렬되지 않은 배열에서 정렬을 하며 새로운 배열에 값을 추가해야 하기 때문에 두 개의 배열이 필요합니다.

 

삽입 정렬은 기존의 정렬되지 않은 배열에서 index 순서대로 새로운 배열에 작은 값이 앞으로, 큰 값이 뒤로 오는 방식으로 값을 추가하며 정렬합니다.

 

그러기 위해서는 자신이 삽입될 위치를 찾는 함수가 필요합니다. 

def findIsertIdx(array, data):
	findIdx = -1		#없는 위치로 초기값을 설정한다.
    for i in range(0, len(array)):
    	if array[i] > data:
        	findIdx = i	#data보다 큰 array의 요소를 찾으면 findIdx로 설정
            break
    if findIdx == -1: 		#data보다 큰 값이 없음
    	return len(array)	#마지막 위치 return
    else:
    	return findIdx

for문을 순회하며 자신이 삽입될 위치를 찾는 함수입니다.

자신보다 큰 값이 array에 존재하면 그 값 앞에 삽입됩니다.

자신보다 큰 값이 array에 존재하지 않으면 마지막 위치에 삽입됩니다.

 

 

def findInsertIdx(array, data):
	findIdx = -1		#없는 위치로 초기값을 설정한다.
    for i in range(0, len(array)):
    	if array[i] > data:
        	findIdx = i	#data보다 큰 array의 요소를 찾으면 findIdx로 설정
            break
    if findIdx == -1: 		#data보다 큰 값이 없음
    	return len(array)	#마지막 위치 return
    else:
    	return findIdx
        
before = [188, 162, 168, 120, 50, 150, 177, 185]
after = []

print('정렬 전 -->', before)
for i in range(len(before)):
	data = before[i]
    insertIdx = findInsertIdx(after, data)
    after.insert(insertIdx, data)
print('정렬 후 -->', after)

정렬 전 --> [188, 162, 168, 120, 50, 150, 177, 185]

정렬 후 --> [50, 120, 150, 162, 168, 177, 185, 188]

위에서 구현한 findInsertIdx 함수를 이용하여 삽입정렬 전체를 구현했습니다.

for문을 순회하며 after에 insert되는 방식으로 정렬이 됩니다.

 

---

삽입 정렬도 선택 정렬과 마찬가지로 이중for문을 사용하기 때문에 알고리즘의 시간복잡도는 $O(n^2)$이 됩니다.