선택 정렬 알고리즘 성능을 분석합시다.
선택 정렬(base:컬렉션,n:원소 개수,compare:비교 논리)
반복(i:=n; i>1 ; i:= i-1)
반복(max=0,j:=1; j<i ; j:=j+1)
조건(compare(base[max], base[j]) < 0)
max := j
temp: = base[i-1]
base[i-1] = base[max]
base[max] = temp
n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 선택 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 할 때 S(n)=n-1입니다. 따라서 T’(n)은 다음과 같습니다.
T'(n) = S(n) + S(n-1) + … + S(2) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1
따라서 선택 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.
n 개의 원소인 배열을 정렬할 때 교환에 걸리는 수행 시간을 T”(n)이라고 합시다. 선택 정렬의 외부 반복문에서 매 번 교환하므로 T”(n)은 다음과 같습니다.
T”(n) = 1 + 1 + … + 1 = n-1
따라서 선택 정렬의 교환에 걸리는 시간은 O(n)입니다. 그리고 선택 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.