-
28. 파이썬 - 선택 정렬(selection sorting)Python/파이썬 자료구조 알고리듬 2019. 6. 22. 13:41반응형
불안정 정렬입니다.
([A1, A2]를 'A를 기준'으로 '숫자를 무시'하고 정렬했을 때
A1, A2의 순서가 바뀔 수 있습니다.)[A, B, A, C, A] 를 정렬하면 [A, A, A, B, C]가 되는데..
A,A,A 간 순서가 어떻게 되든 무슨 상관이냐 라고 생각할 수 있는데..[A1, B2, A2, C1, A3] 의 경우 숫자를 기준으로 한번 정렬한 뒤,
[A1, C1, B2, A2, A3] 문자를 기준으로 한번 정렬해서,
[A1, A2, A3, B2, C1] 를 만들어야 할 경우도 있기 때문에 중요합니다.1. 선택 정렬은 리스트의 첫 요소를 최저값으로 정한 뒤
2. 리스트의 끝까지 최저 값을 찾습니다.
3. 최저값이 있으면 최저값과 첫 요소를 교환합니다.
4. 첫 요소는 최저값이 되었으니, 두 번째 요소를 최저값으로 정한 뒤 반복합니다.
def selection_sort(array): """선택 정렬""" length = len(array) for outer in range(length - 1): min_val = outer for inner in range(outer + 1, length): if array[min_val] > array[inner]: min_val = inner if min_val != outer: array[outer], array[min_val] = array[min_val], array[outer] print(outer, min_val, array) selection_sort([8, 5, 4, 2, 6])
0 3 [2, 5, 4, 8, 6] 1 2 [2, 4, 5, 8, 6] 3 4 [2, 4, 5, 6, 8]
반응형