Selection Sort - 선택 정렬

매번 가장 작은 원소를 선택한다.

• 정렬하고자 하는 대상의 첫 원소와 다음 원소를 비교하는 것을 시작한다.
• 그리고 매번 가장 작은 원소를 찾아 순서대로 정렬한다.

import sys
from random import shuffle

input = sys.stdin.readline

N = int(input())
lst = [_ for _ in range(1, N + 1)]
shuffle(lst)

print("정렬 전 : {}".format(lst))

# selection sort
for i in range(N - 1):
    # i 번째 위치에 올 가장 작은 원소를 찾는다.
    idx = i 
    for j in range(i + 1, N):
        if lst[idx] > lst[j]:
            idx = j

    lst[i], lst[idx] = lst[idx], lst[i]
    
print("정렬 후 : {}".format(lst))