선택정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식
• 정렬 과정
  • 주어진 리스트 중에서 최소값을 찾는다.
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
  • 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.
• 시간 복잡도 : O(n^2)

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

1. 최소값을 i인덱스로 지정한다.
2. i+1부터 배열을 돌면서 최소인덱스를 찾는다.
3. 리스트의 맨 앞과 교환한다.
4. 미정렬 i가 증가함에 따라, 정렬된 부분과 미정렬된 부분이 나뉘어지고 계속 최소값을 찾아 미정렬 부분의 첫번째로 보낸다.