선택 정렬

---

• 다음과 같은 순서를 반복하며 정렬한다.
  1. 주어진 데이터 중에 최소값을 찾는다.
  2. 최소값을 데이터의 맨 앞에 위치한 값과 교체한다.
  3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

시간 복잡도

• 반복문이 두 개이므로 시간 복잡도는 $O(n^2)$이다.

구현

---

def SelectionSort(data_list):
    for i in range(len(data_list) - 1):
        min_index = i
        for j in range(i+1, len(data_list)):
            if data_list[min_index] > data_list[j]:
                min_index = j
        data_list[i], data_list[min_index] = data_list[min_index], data_list[i]
    return data_list