알고리즘 / 삽입 정렬

학습 도서

이것이 코딩테스트다 with 파이썬 (한빛미디어, 나동빈 저)

 

 

정렬(Sorting)

 

- 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

- 예시 : 오름차순, 내림차순

- 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 

 

삽입 정렬(Insertion Sort)

 

- 컨셉 : 순서대로 데이터를 확인하며 적절한 위치에 삽입한다.

- 알고리즘

 1) 첫 번째 데이터는 그대로 둔다.

 2) 두 번째 데이터가 첫 번째 데이터보다 큰 지 판단한다.

 3) 크다면 그대로 두고, 작다면 첫 번째 데이터의 앞으로 옮긴다.

 4) 세 번째 데이터가 두 번째 데이터보다 큰 지 판단한다.

 5) 크다면 그대로 두고, 작다면 두 번째 데이터 앞으로 옮긴다.

 6) 만약에 세 번째 데이터를 두 번째 데이터 앞으로 옮겼다면 첫 번째 데이터보다 큰 지 판단한다.

 7) 크다면 그대로 두고, 작다면 첫 번째 데이터 앞으로 옮긴다.

 8) 네 번째 데이터가 세 번째 데이터보다 큰 지 판단한다.

 ...

 

 

전체 소스 코드

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]
        else :
        	break
            
 print(array)
 

 

 

해설

 

코드를 차근차근 살펴보자.

 

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

- Goal : 위의 데이터들을 오름차순으로 나열하자.

 

for i in range(1, len(array)):

- len(array) = 10

- range(1, len(array)) = [1,2,3,..,9]

(포스팅 참고 :   1y9u9j2in.tistory.com/152?category=910442 )

- i = 1, 2, 3, ..., 9

 

for j in range(i,0,-1):

- range(i, 0, -1) : i부터 0까지 1씩 감소하며 나열되는 배열

- i = 1, range(i, 0, -1) = [1, 0]

  - j =1, 0

- i = 2, range(i, 0, -1) = [2, 1, 0]

  - j = 2, 1, 0

 ...

- i = 9, range(i, 0, -1) = [9, 8, 7, ..., 2, 1, 0]

  - j = 9, 8, ..., 0

 

    	if array[j] < array[j-1]:
        	array[j], array[j-1] = array[j-1], array[j]
        else :
        	break

- i =1, j = 1,

  array[1] < array[0] 이므로 array[1], array[0] 은 서로 자리를 바꾼다.

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

- i =2, j = 2,

  array[2] > array [1] 이므로 break

- i = 2, j = 1,

  array[1] > array[0] 이므로 break

- i = 3, j = 3,

  array[3] < array[4] 이므로 서로 자리를 바꾼다.

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

- i = 3, j= 2,

  array[2] < array[1] 이므로 서로 자리를 바꾼다.

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

- i = 3, j= 1,

  array[1] < array[0] 이므로 서로 자리를 바꾼다.

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

...

 

 print(array)

 

- 오름차순 완성