[C언어 알고리즘] 2.6.1 쉘 정렬 알고리즘 성능 분석

[C언어 알고리즘] 2.6.1 쉘 정렬 알고리즘 성능 분석

---

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

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

    반복(step:=size/2;  step>0  ; step:=step/2)

        반복(i:=0; i<step ; i:=i+1)

            삽입정렬2(base+i, size-n, step)

 

삽입정렬2(base:컬렉션, size:원소 개수, step:간견)

    반복(i:=step;  i<size  ; i:= i+step)

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

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

                temp: = base [j-step]

                base[j-step] = base [j]

                base[j] = temp

            아니면

                루프 탈출

 

쉘 절렬의 내부 반복문의 수행 시간은 삽입 정렬2를 수행하는 시간입니다. 삽입 정렬2의 수행 시간을 S(n,step)이라고하면 쉘 정렬에 걸리는 시간은 다음과 같습니다.

T(n) = S(n, n/2) + S(n, n/4) + S(n, n/8)+...+S(n,1)

 

삽입 정렬2의 수행 시간을 알아봅시다. n 개의 원소인 배열을 step 간격으로 정렬할 때 비교에 걸리는 수행 시간을 S(n,step)입니다. 삽입 정렬2의 내부 반복문에서 비교에 걸리는 시간을 T' (n, step)이라고 가정합시다. 내부 반복문은 n/step만큼 수행합니다. 따라서 T' (n,step) = n/step입니다.

 

삽입 정렬2의 수행 시간은 다음과 같습니다.

S(n,step) = T' (step,step) + S(2*step, step) + ... + S(n,step) = 1 + 2 + 3 + ... +step

 

따라서 쉘 정렬에 걸리는 시간은 다음과 같습니다.

T(n) = S(n, 2/n) + S(n, 4/n) + S(n, 8/n) + ... + S(n,1)

= (1 + 2 + 3 + ... +n/2) + (1 + 2 + 3 + ... +n/4) + (1 + 2 + 3 + ... +n/8) + ... + 1

 

이처럼 쉘 정렬을 수행하는 시간을 계산하는 것은 까다롭습니다. 일반적으로 삽입 정렬의 수행 시간은 O(n^1.5)라고 말합니다.