Sorting Algorithm - 삽입정렬(insert sort)

• 선택정렬에 비해 실행시간 측면에서 효율적이고, 선택정렬처럼 동작원리가 간단함.
• 삽입정렬은 필요할때만 위치를 바꾸므로 데이터가 거의 정렬되었을 때 효율적
• (한 사이클에) 정렬되어진 원소들은 항상 오름차순을 유지한다.

 

** 첫번째 원소는 정렬되있다 가정하고, 두번째 원소부터 시작.

      정렬됨.

      정렬할 원소

7

5

9

0

3

1

정렬할 원소 5는 정렬된 원소 7보다 작으므로 정렬한 원소 7 왼쪽으로 이동(7과변경)

5

7

9

0

3

1

 

---

 

 

5

7

9

0

3

1

 

정렬할 원소 9는 정렬된 원소 9보다 크므로 이동하지 않고 그대로 위치

5

7

9

0

3

1

 

---

 

5

7

9

0

3

1

 

정렬할 원소 0는 정렬된 원소 9보다 작으므로 정렬한 원소 7 왼쪽으로 이동

5

7

0

9

3

1

 

정렬할 원소 0은 정렬된 원소 7보다 작으므로 정렬한 원소 7 왼쪽으로 이동

5

0

7

9

3

1

 

정렬할 원소 0은 정렬된 원소 5보다 작으므로 정렬한 원소 5 왼쪽으로 이동

0

5

7

9

3

1

0

5

7

9

3

1

 

 

 

같은 로직으로 계속...

 

 

---

 

삽입정렬의 로직을 다음과 같이 생각하면 알고리즘 구현하는데 쉽다.

 

• 첫번째 원소는 정렬되어있다고 생각하고 두번째 원소부터 정렬을 시작한다.
• i 번째 원소는 i-1 번째 원소부터 1번째 까지 비교하며 이동한다.  i 번째 요소가 (i-1)번째 요소보다 작으면 SWAP 한다.
• 정렬된 원소의 위치는 1씩 증가하고 동시에 비교할 원소도 1개씩 증가한다.
• 비교할 원소들은 1씩 증가, 비교 순서는 역순.

# PYTHON

array = [7, 5, 9, 0, 3, 1]

for i in range(1,len(array)): # 두번째 원소부터(index 1)
	for j in range(i,0,-1): # 역순으로 이동
    	if (j[i] < j[i-1]): # 이동하면서 값 비교
        	array[j], array[j-1] = array[j-1]. array[j]
        else: # 비교중지
        	break;