동작 방식
배열에서 앞에 값들 중 적절한 곳에 위치 시킨다.
ex> [10, 5, 1] 의 배열이라 가정
- 10은 맨 앞의 값이라 건너 뛴다.
- 5는 앞의 값 10의 앞 또는 뒤 두 곳중 한 곳에 갈 수 있다.
- 해당 값은 10보다 작으므로 10을 뒤로 밀고 [5, 10, 1]로 만든다.
- 1은 맨 앞, 5와 10 사이 그리고 10 뒤에 세 곳중 한 곳에 갈 수있다.
- 1은 가장 작으니 맨앞으로 가고 나머지를 뒤로 밀어준다. [1, 5, 10]
특징
동작 하는 기준 값의 앞에 있는 배열은 이미 정렬되어 있다는 가정하에 작업한다.
장점
- 특징 때문에 일반적으로 버블정렬이나 선택 정렬 보다 빠르다.
- 배열이 거의 정렬이 되어 있는경우 O(NlongN)의 복잡도를 가지는 배열(퀵, 병합, 힙)보다도 빠르다.
시간 복잡도
O(N*N)
- 추론 1 : 10 + 9 + 8 ... +1 번 비교 작업
- 추론 2 : N(N+1)/2
- 추론 3 : '/2'는 N이 엄청 큰 수라고 가정 했을 경우 의미 없는 값으로 처리한다
- 결론 : 시간 복잡도는 N*N
동작 순서 예시
[10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
[5, 10, 1, 8, 4, 3, 2, 9, 6, 7]
[1, 5, 10, 8, 4, 3, 2, 9, 6, 7]
[1, 5, 8, 10, 4, 3, 2, 9, 6, 7]
[1, 4, 5, 8, 10, 3, 2, 9, 6, 7]
[1, 3, 4, 5, 8, 10, 2, 9, 6, 7]
[1, 2, 3, 4, 5, 8, 10, 9, 6, 7]
[1, 2, 3, 4, 5, 8, 9, 10, 6, 7]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 24
@ Update : 2020. 01. 24
@ Description : Insertion sort (삽입 정렬)
'''
def fn_swapping(list_target, int_index_a, int_index_b):
'''
@Description: List index swapping
@Arguments Example
list_target = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
int_index_a = 0
int_index_b = 2
'''
value_tmp = list_target[int_index_a]
list_target[int_index_a] = list_target[int_index_b]
list_target[int_index_b] = value_tmp
return list_target
def fn_insertion_sort(list_input):
'''
@Description: Insertion sort (삽입 정렬)
@Arguments Example
list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
'''
int_len_list_input = len(list_input)
for int_list_input_index in range(int_len_list_input):
for int_index in range(0, int_list_input_index):
if list_input[int_index] > list_input[int_list_input_index]:
value_tmp = list_input[int_list_input_index]
for int_move_index in range(int_list_input_index - int_index):
list_input = fn_swapping(list_input, int_list_input_index - int_move_index, int_list_input_index - int_move_index - 1)
list_input[int_index] = value_tmp
break
print(list_input)
if __name__ == "__main__":
list_fn_insertion_sort_param = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
fn_insertion_sort(list_fn_insertion_sort_param)