선택 정렬 시간복잡도

1. 각 반복마다 최소값 찾기

탐색 횟수는 n번 탐색에서 1번 탐색할때까지 감소

n + n-1 +  n-2 + ... + 2 + 1 = 등차수열 (n^2+n/2)

 

2. swap 

상수(c)시간안에 끝남 , n번 호출

c * n

 

3. 나머지 연산들

마찬가지로 상수시간안에 끝남(c), n번 호출

c *n

 

합산 결과  = n^2+ n/2 + c*n + c*n = θ(n^2)

 

선택 정렬은 best 케이스 이든 worst케이스이든 최소값 찾는 범위는 바뀌지 않는다.

따라서 입력 크기 n에 관계없이 θ(n^2)