28. 파이썬 - 선택 정렬(selection sorting)

불안정 정렬입니다. 

 

([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]