[알고리즘 공부] 삽입정렬

오늘의 알고리즘은 삽입정렬입니다. 삽입정렬은 처리되지 않은 데이터를 골라 적절한 위치에 삽입합니다. 사실 오늘 포스팅하는 삽입 정렬 알고리즘을 포함해서 대다수의 정렬 알고리즘들은 아마 실무에서는 사용하는 일이 없을 거라고 생각됩니다. 그만큼 언어 내장 정렬 알고리즘이 강력하다는 의미겠죠. 하지만 정렬 알고리즘에 어떤 알고리즘이 있고, 어떻게 동작하는지 알아두는 것은 중요하다고 생각합니다.  

 

삽입정렬 시간복잡도

삽입정렬의 시간복잡도는 2중 for문을 사용하기 때문에O(n^2)입니다. 하지만 현재 리스트의 데이터들이 거의 정렬되어 있는 상태이면 매우 빠르게 동작하며, 최선의 경우 O(n)의 시간복잡도를 가지고 있습니다.

 

선택정렬 코드

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
print(array)

출력결과는 당연히 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 가 될 것입니다.