[C언어 알고리즘] 2.5.1 삽입 정렬 알고리즘 성능 분석

[C언어 알고리즘] 2.5.1 삽입 정렬 알고리즘 성능 분석

---

 삽입 정렬 알고리즘 성능을 분석합시다.

삽입 정렬(base:컬렉션, n:원소 개수, compare:비교 논리)

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

        반복(j=i; j>0 ; j:=j-1)

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

                temp: = base [j-1]

                base[j-1] = base [j]

                base[j] = temp

            아니면

                루프 탈출

 

 n 개의 원소인 배열을 정렬할 때 비교에 걸리는 수행 시간을 T'(n)이라고 합시다. 삽입 정렬의 내부 반복문에서 비교에 걸리는 시간을 S(n)이라고 하면 S(n) = n-1입니다. T'(n)은 다음과 같습니다.

T'(n) = S(2) + S(3) + ... + S(n) = 1 + 2 + 3 + ... +(n-1)

 

 따라서 삽입 정렬의 비교에 걸리는 시간은 O(n^2)이라고 말할 수 있습니다.그리고  삽입 정렬에서 교환과 비교 횟수는 같습니다. 따라서 선택 정렬 알고리즘을 수행 시간은 O(n^2)이라고 말할 수 있습니다.