[파이썬][알고리즘] 선택 정렬 (selection sort)

선택 정렬 (selection sort)

선택 정렬이란

• 데이터에서 최솟값을 찾아 가장 맨 앞에 위치한 값과 교체하는 방법
  • 참조 (visualgo.net/en/sorting)

• 데이터의 길이가 n일 때 총 n-1번 시행을 한다.
• 반복문을 돌면서 가장 작은 수가 들어있는 인덱스를 저장할 변수를 만든다.
• 반복문을 시행한 뒤 자리바꿈을 실행한다.

def selection_sort(data):
    for trial in range(len(data) - 1):
        first = trial
        for i in range(trial + 1, len(data)):
            if data[first] > data[i]:
                first = i
        data[first], data[trial] = data[trial], data[first]
    return data

import random

num = random.sample(range(100), 10)
print(num)
print(selection_sort(num))

[47, 40, 63, 73, 24, 54, 69, 82, 87, 1]
[1, 24, 40, 47, 54, 63, 69, 73, 82, 87]

시간 복잡도 O($n^2$)