알고리즘 : 삽입 정렬(insertion sort)

삽입 정렬(insertion sort)은?

• 두 번째 인덱스부터 시작함
• 해당 인덱스(key값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사함
• key 값이 더 큰 데이터를 만날때까지 반복, 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동함

출처 : 위키미디어

for index in range(10, 1, -1)
print(index)

"""
출력결과
10
9
8
7
6
5
4
3
2
"""

 

데이터가 4개 일 때 동작 

data_list = [8, 4, 3, 5]
처음 한 번 실행하면, key값은 8, 인덱스(0) -1은 0보다 작음, 끝 : [8, 4, 3, 5]
두 번째 실행하면, key값은 4, 8보다 4가 작음 자리바꿈, 끝 : [4, 8, 3, 5]
세 번째 실행하면, key값은 3, 8보다 3이 작음 자리바꿈, 다시 4보다 2가 작음, 끝 : [3, 4, 8, 5]
네 번째 실행하면, key값은 5, 8보다  5가 작음 자리바꿈, 4보다는 5가 큼, 끝 : [3, 4, 5, 8]

 

알고리즘 구현

1. for stand in range(len(data_list)) 로 반복

2. key = data_list[stand]

3. for num in range(stand, 0, -1) 반복

• 내부 반복문 안에서 data_list[stand] < data_list[num - 1]이면,
  data_list[num - 1], data_list[num] = data_list[num], data_list[num - 1]

def insertion_sort(data):
	for index in range(len(data) - 1):
    	for index2 in range(index + 1, 0, -1):
        	if data[index2] < data[index2 - 1]:
            	data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
            	break
    return data
    

#랜덤으로 출력
import random

data_list = random.sample(range(100), 50)
print(insertion_sort(data_list))

#출력결과 
[1, 2, 3, 5, 8, 9, 10, 11, 14, 16, 17, 20, 22, 23, 32, 33, 34, 36, 40, 43, 46, 47, 
49, 50, 51, 53, 56, 57, 60, 61, 62, 64, 65, 67, 68, 71, 72, 74, 75, 81, 82, 83, 85, 
86, 89, 90, 91, 93, 96, 99]

 

알고리즘 분석

• 반복문이 두 개 O(n²)
• 최악의 경우 n*(n-1) / 2
• 완전 정렬이 되어 있는 상태면 최선은 O(n)