쉘 정렬 알고리즘 성능을 분석합시다.
쉘 정렬(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)라고 말합니다.