선택 정렬(Selection Sort)

전개

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 값을 맨 앞의 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
4. 마지막 차례에서는 다음에 비교할 값이 없으므로 그 전에 반복문을 미리 끝낸다.

시간 복잡도

• O(${N^2}$)

구현 코드

def selection_sort(numbers):
    """오름차순 선택 정렬을 실행합니다."""
    n = len(numbers)

    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if numbers[j] < numbers[min_idx]:
                min_idx = j

        numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]

    selection_sort(numbers)

    print(numbers)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
'''

Ref

• 선택 정렬