Shellsort,2.48 ^(k-1)vs Tokuda的序列

Question

介绍

Shellsort是一个有趣的排序算法,我刚才遇到过.最令人惊讶的是,不同的间隙序列可以显着提高算法的速度.我做了一些阅读(不广泛),似乎Tokuda的序列被推荐用于实际应用.

另一个有趣的部分是比率2.20~2.25的顺序往往更有效.所以我做了一个小搜索,考虑了从2.20到2.50的比率序列,并尝试搜索哪个比率可以表现平均好.我遇到了这个比例:2.48在许多不同的试验中看起来平均表现良好.

然后,我想出了序列发生器:2.48 ^k-1(让它称之为248序列)并试图将它与Tokuda的序列进行比较.事实证明,它们的平均速度相等.248个序列倾向于使用稍多的比较数.

基准方法

• 我使用比较次数和交换次数,而不是使用毫秒作为度量.
• 我按照以下阵列大小(50,000; 100,000; 200,000; 300,000; 500,000; 1,000,000)进行了100次试验,并跟踪它们的比较次数和交换次数.
• 以下是我的数据(此处为CSV格式).
• 完整代码:http://pastebin.com/pm7Akpqh

问题

我知道我可能错了,这就是为什么我来这里寻求更有经验的程序员的更多意见.如果你没有得到问题,这是我的问题:

• 2.48 ^k-1和Tokuda的序列一样好吗？
• 如果它与Tokuda的序列一样好,使用它会更实用,因为2.48 ^k-1序列比Tokuda的序列更容易生成.

---

248 Sequence:
  ROUNDUP ( 2.48(k-1) )
  eg: 1, 3, 7, 16, 38, 94, 233, 577, 1431, 3549, 8801, 21826, ...

Tokuda's Sequence
  ROUNDUP ( (9k - 4k) / (5 * 4k - 1) )
  eg: 1, 4, 9, 20, 46, 103, 233, 525, 1182, 2660, 5985, 13467, ...

---

正如@woolstar建议我也测试边缘情况,如反转和排序.正如预期的那样,248序列在边缘情况下更快,因为248序列间隙更大,因此它更快地移动逆.

---

Shellsort实施

public static int compare = 0;
public static int swap = 0;

public static bool greaterthan(int a, int b) {
    compare++;
    return a > b;
}

public static int shellsort(int[] a, int[] gaps) {
    // For keeping track of number of swap and comparison
    compare = 0;
    swap = 0;

    int temp, gap, i, j;

    // Finding a gap that is smaller than the length of the array
    int gap_index = gaps.Length - 1;
    while (gaps[gap_index] > a.Length) gap_index--;

    while (gap_index >= 0) {

        // h-sorting
        gap = gaps[gap_index];
        for (i = gap; i < a.Length; i++) {
            temp = a[i];
            for(j = i; (j >= gap) && (greaterthan(a[j - gap], temp)); j -= gap) {
                a[j] = a[j - gap];
            }

            // swapping
            a[j] = temp;
            swap++;
        }

        gap_index--;
    }

    return compare;
}

Answer 1

根据这项研究：（Ciura, Marcin (2001)“Best Increments for the Average Case of Shellsort”。In Freiwalds, Rusins。第 13 届国际计算理论基础研讨会论文集。伦敦：Springer-Verlag。第 106 页\ xe2\x80\x93117)对于大小小于 10 ^{8 个}元素的数组，希尔排序中的主要操作应该是比较操作，而不是交换：

\n\n

\n

Knuth\xe2\x80\x99s 的讨论假设运行时间可以近似为 9\xc3\x97 次移动，\n 而图 3 和图 4 显示，对于每个序列，键比较的次数是运行时间的更好衡量标准比移动次数。^{对于 N \xe2\x89\xa4 10 8}来说，每次移动 9 个周期的渐近比率不太精确，并且，如果某个假设序列使 \xce\x98(NlogN) 移动，则永远无法实现。其他计算机体系结构的类似图会得出相同的结论。

\n\n

将移动视为主导操作会导致关于最佳序列的错误结论。

\n

\n\n

在这种情况下，你的问题的答案是否定的：248 序列更糟糕，因为它使用了更多的比较。您还可以考虑将您的序列与本文中介绍的 Ciura 序列进行比较，因为这项研究似乎证明它比 Tokuda 序列更好。

\n