선택 정렬(selection sort)

선택 정렬은 모든 $i$에 대해 $A[i…N-1]$에서 가장 작은 원소를 찾은 뒤, 이것을 $A[i]$에 넣는 것을 반복합니다.

찾는 과정이 inner for loop, 시간 복잡도는 $O(N)$이기 때문에 선택 정렬은 최악의 경우와 최선의 경우 모두 $O(N^2)$의 시간 복잡도를 가지게 됩니다.

시간 복잡도

	Best	Average	Worst
선택 정렬(Selection Sort)	$O(N^2)$	$O(N^2)$	$O(N^2)$

코드

def selectionSort(A):
    for i in range(len(A)):
        minIndex = i
        for j in range(i+1, len(A)):
            if A[minIndex] > A[j]:
                minIndex = j
        # swap
        temp = A[i]
        A[i] = A[minIndex]
        A[minIndex] = temp

동작 과정