정렬 알고리즘 (2) - 삽입 정렬

삽입 정렬 : 특정한 데이터를 적절한 위치에 삽입한다는 의미로, 그 앞의 데이터는 이미 정렬되어 있다고 가정한다.

 

 

아래와 같은 배열이 있다고 하자.

*** 핑크색은 이미 정렬된 데이터

 

 

삽입 정렬은 두번째 데이터부터 시작한다. 첫번째 데이터는 이미 정렬되어 있다고 가정하기 때문이다.

step1. 두번째 데이터 5가 어떤 위치에 삽입되어야 하는지 판단한다. 7의 앞에 갈지 뒤에 갈지 선택지는 2개이다. 5는 7보다 작기 때문에 7의 왼쪽에 삽입한다.

 

step2. 9가 어떤 위치에 삽입되어야 하는지 판단한다.  선택지는 3개이지만 9는 7보다 크기 때문에 그대로 둔다.

 

step3. 0이 어떤 위치에 삽입되어야 하는지 판단한다. 0은 5보다 작기 때문에 5의 왼쪽에 삽입한다.  

 

위의 과정을 반복하면 

정렬이 된 배열을 얻을 수 있다.

 

 

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): #정렬된 데이터에서 어디 삽입할 지 판단
    	if(array[j]<array[j-1]): #한칸씩 왼쪽으로 이동
        	array[j],array[j-1] = array[j-1], array[j] #swap
        else: #자기보다 작은 데이터를 만나면 그 위치에서 멈춤
        	break
print(array)      
        	
    	

 

코드를 작성하면 이렇다 ~~