An analysis of (h,k,l)-shellsort

[摘要] One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let $\vec{h} be a t-component vector of positive integers. An $\vec{h}$-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let $S_j$($\vec{h}$;n) denote the average number of element exchanges in the j-th pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of $S_j$($\vec{h}$;n) for any fixed $\vec{h}$ = (h,k,l), making use of a new combinatorial interpretation of $S_3$. For the special case $\vec{h}$ = (3,2,1), the analysis if further sharpened to yield exact expressions.

[学科分类] 计算机科学（综合）