[디딤돌 자료구조와 알고리즘 with C] 2.3.1 선택 정렬 알고리즘 성능 분석

2.3.1 선택 정렬 알고리즘 성능 분석

 선택 정렬 알고리즘 성능을 분석합시다.

선택 정렬(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)이라고 말할 수 있습니다.

2.3 선택 정렬 알고리즘

2.3.2 선택 정렬 알고리즘 구현