[알고리즘] Selection Sort(선택정렬)

selection sort란 수를 정렬하는 방식 중 가장 원시적인 정렬 알고리즘으로 가장 작은 수를 찾아낸 다음 앞으로 보내는 방식의 정렬 방법입니다.
정렬방식 중 가장 기본적인 정렬방식입니다.

위 그림에서 보다시피 정렬되지 않은 부분에서 최소값을 찾아 앞으로 보내 차례대로 정렬하는 것입니다.

(귀찮아서 손으로 그린건 안비밀)

그렇다면 선택정렬을 하기위해선 몇 번의 연산이 필요할까요?

N개의 수가 있다면 처음 최솟값을 구해 정렬하는데 N번, 두번째는 N-1번 세번짼 N-2번 ... 마지막 한번까지

N! 번 연산이 필요합니다

이는 공차가 -1인 등차수열로 n(n+1)/2의 공식을 가집니다. 따라서 시간복잡도는 O(N^2)을 가지게 되고 N의 개수가 많아질수록

효율이 굉장히 떨어지게됩니다 ㅠㅠ 따라서 처리해야할 데이터의 개수가 많을 때는 사용하지 않는 것이 좋을 것 같습니다

아래는 파이썬으로 짠 선택정렬 코드입니다.

import sys

numbers = list(map(int,sys.stdin.readline().split()))

for i,v in enumerate(numbers):
    mini = min(numbers[i:])
    m_index = i + numbers[i:].index(mini)
    numbers[i],numbers[m_index] = mini,v

print(numbers)