arrays - 用于对包含 32 个随机元素的列表进行排序的自适应排序算法与排序网络

Question

如果我们使用的是按顺序进行比较的顺序机器(不可能进行并行比较)，并且我们希望在对 32 个随机元素进行排序时最大限度地减少处理器时钟周期的数量，那么我们应该使用排序网络还是自适应排序算法？

对于 n=32 个元素，目前还没有最佳网络。实际上，如果我们想最小化 CPU 时钟周期数，最好将 32 个元素分成四个 n=8 的子列表，并在每个子列表上应用最优排序网络，然后将列表合并在一起？

我们显然在这里使用“平均性能”，因为如果给定一个已经排序的列表，自适应算法会很幸运。

处理数字我们有以下内容:

对大小为 n 的列表进行排序:

• n=2 的最小比较次数为 1。

• n=4 的最小比较次数为 5。

• n=8 的最小比较次数为 19。

合并两个大小为 n 的列表:

• 合并两个 n=2 的列表是 2*n - 1 = 3 次比较

• 合并两个 n=4 的列表是 2*n - 1 = 7 次比较

• 合并两个 n=8 的列表是 2*n - 1 = 15 次比较。

• 合并两个 n=16 的列表是 2*n - 1 = 31 次比较。

如果我们将 n=32 分成 16 个 n=2 子列表，则比较的总数:

• 排序:1*16 = 16
• 合并:3*8 + 7*4 + 15*2 + 31*1 = 113
• 总计:129

如果我们将 n=32 分成八个 n=4 子列表，则比较的总数:

• 排序:5*8 = 40
• 合并:7*4 + 15*2 + 31*1 = 89
• 总计:129

如果我们将 n=32 分成四个 n=8 的子列表，则比较的总数:

• 排序:19*4 = 76
• 合并:15*2 + 31*1 = 61
• 总计:137

现在人们可能会认为将 n=32 个元素分成 n=2 或 n=4 个子列表会更好，因为比较的总数更少。但是 mergin 需要存储数组的一部分“不在适当的地方”，这可能会抵消较少比较的好处？

我的直觉告诉我，平均而言，非自适应排序网络在总体比较方面与算法相似，但排序网络由于开销较小而获胜，对吗？

---

我试图在平均不到 1200 个时钟周期内对 n=32 个元素进行排序。我在工作on a simple sequential machine使用简单的256 字 * 16 位内存和只有四个寄存器，因此网络/算法必须简单、快速且不需要大量空间。 ALU 只有加、减、一位移位、一位旋转、与和或功能。内存和 ALU 操作各需要一个时钟周期。

Answer 1

堆排序是nlogn。索引计算很简单——要比较的项目始终具有 n, 2n+{1,2 } 的索引，使其在您的架构中计算效率高。

堆排序的主力基本上就是套路:

while(true){
    r=(i+1)*2; l=r-1;
    if (*l > * i) { 
       if (*r > *l) swap(i,r);
       else swap(i,l);
    }
    else { 
       if (*r >* i) swap(i,r);
       else break;
    }
 }

作为副作用，交换操作必须将地址 i 更新为 l 或 r。与教科书解决方案不同，我们不检查 child 的地址是否有效，但我们交换空间以加快在数组末尾分配 32 个零的缓冲区。一旦 i 不大于任何一个 child ，遍历到堆底就结束了。