[알고리즘 C언어] 2.3.1 버블 정렬 알고리즘 성능 분석

버블 정렬 알고리즘 성능을 분석합시다.

버블 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

    반복(i:=n;  i>1  ; i:= i-1)

        반복(j:=1; j<i ; j:=j+1)

            조건(compare(base[j-1], base[j]) > 0)

                교환(base[j-1],base[j])

 

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)이라고 합시다. 버블 정렬의 내부 반복문에서 교환하는 시간을 R(n)이라고 하면 최악일 때 R(n)=n-1입니다. 그리고 T”(n)은 다음과 같습니다.

T”(n) = R(n) + R(n-1) + … + R(2) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1

 

마찬가지로 버블 정렬의 교환에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다. 따라서 버블 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.


학습에 도움이 되시면 ebook을 구입(판매가 3000원, ebook)하여 소장하시면 감사하겠습니다.

언제나 휴일 출판사의 수익금의 대부분은 아프리카에 기부하고 있습니다.

디딤돌 알고리즘 C언어는 디딤돌 자료구조와 알고리즘 with C언어에서 알고리즘 부분을 다루고 있어서 많은 부분에서 비슷합니다.