Optimal gap sequences in Shellsort, defined as gap sequences having the minimised maximum number of comparisons for a fixed number of pairwise distinct elements, are found by minimax search in reduced permutational spaces, namely Bad $(s,1)$-sorted permutations. Exact optimal gap sequences in Shellsort for $n\leq16$ pairwise distinct elements are established, and the best known gap sequences for $17\leq n\leq 30$ are listed with conjectures made. It notably discovers some optimal gap sequences consist of increments larger than the half of the total number of the elements to sort.
翻译:Shellsort 中的最佳差距序列被定义为具有固定数量对称不同元素最大比较次数的最小化差距序列,通过在减少的变异空格中进行微量搜索即可找到,即坏(s,1)美元(s)和(s)美元(sorved)的排列。在 Shellsort 中,对等差异元素的精确最佳差距序列已经确立,17\leq nleq 30美元的最佳已知差距序列被列出为假设值。主要发现一些最佳差距序列包含大于所要分类元素总数一半的递增。