동작 방식
배열 요소를 하나씩 다 비교해서 가장 작은걸 앞으로 보내는 방식
ex> index 0-9 비교 후 가장 작은것 맨앞으로 바꿈
다음 1-9 비교후 가장 작은것 두번째
이 작업을 배열의 수 만큼 반복
단점
효율이 엄청 떨어짐
시간 복잡도
O(N*N)
- 추론 1 : 10 + 9 + 8 ... +1 번 비교 작업
- 추론 2 : N(N+1)/2
- 추론 3 : '/2'는 N이 엄청 큰 수라고 가정 했을 경우 의미 없는 값으로 처리한다
- 결론 : 시간 복잡도는 N*N
동작 순서 예시
[1, 5, 10, 8, 4, 3, 2, 9, 6, 7]
[1, 2, 10, 8, 4, 3, 5, 9, 6, 7]
[1, 2, 3, 8, 4, 10, 5, 9, 6, 7]
[1, 2, 3, 4, 8, 10, 5, 9, 6, 7]
[1, 2, 3, 4, 5, 10, 8, 9, 6, 7]
[1, 2, 3, 4, 5, 6, 8, 9, 10, 7]
[1, 2, 3, 4, 5, 6, 7, 9, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
python3 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 23
@ Update : 2020. 01. 23
@ Description : Selection 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_selection_sort(list_input):
'''
@Description: Selection 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):
int_min_index = int_list_input_index
int_min = list_input[int_list_input_index]
for int_index in range(int_list_input_index + 1, int_len_list_input):
if int_min > list_input[int_index]:
int_min_index = int_index
int_min = list_input[int_min_index]
list_input = fn_swapping(list_input, int_list_input_index, int_min_index)
print(list_input)
if __name__ == "__main__":
list_fn_selection_sort_param = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
fn_selection_sort(list_fn_selection_sort_param)