- 정렬된 왼쪽 부분과 정렬되지 않은 오른쪽 부분으로 나뉜다
초기에 왼쪽 부분은 비어있고, 오른쪽 부분은 가득 차 있다.
- 오른쪽 부분에서 가장 작은 값을 구한 후 이를 왼쪽 부분으로 이동시킨다
왼쪽에는 데이터가 작은 수부터 하나씩 추가된다
오른쪽 부분에 데이터가 없을 때까지 반복한다
def selection_sort(n):
nl = len(n)
for i in range(nl-n):
if n[j] < n[least]:
least = j
n[i], n[least] = n[least] n[i]복잡도
- 비교 횟수 : O(n^2) 으로 고정
- 이동 횟수 : 3(n-1)
- 전체 시간복잡도 : O(n^2)
