Y批次X号排序算法

Question

有人能告诉我一种算法吗?我可以用它来对Y数进行批次排序，这意味着你只能同时比较Y数，但是你可以多次这样做。

例如，有X=100语句，应答者必须根据它们对她的相关性对它们进行排序，这样她一次只能看到和排序Y=9语句，但会多次这样做。

Answer 1

从你的假设，我相信你愿意做很多工作来找出下一个比较集(因为那是由计算机完成的)，并且希望尽可能少的比较(因为那是一个人)。

因此，我将描述的方法的想法是一个贪婪的启发式方法，它试图最大限度地利用每个比较所提供的信息。这很复杂，但应该做得很好。

我们首先需要的是如何测量信息。这是数学理论。假设我们有一个有偏见的硬币，它有可能出现在p头上。上面提到的信息是- log2(p)。它后面的信息是- log2(1-p)。(注意，0到1之间的数字的log是负的，负的是正的。)因此，信息总是积极的。如果您使用高效的编码，并且有许多翻转来编码，那么一个翻转序列的信息之和就是您需要发送多少位来进行通信。

因此，期望一次翻转的信息是- p log2(p) - (1-p) log2(1-p)。

所以我们的想法是选择一个比较集，这样排序就能给我们提供尽可能多的关于我们还没有的最后一种类型的信息。但是，我们如何估计对某一对不知道多少呢？例如，如果我对2组5中的组进行排序，那么其中一组的顶部不可能小于另一组的底部。可能是这样，但相比于将两个中间元素相互比较，这种比较中的信息要少得多。我们怎么捕捉到这个？

我对如何做到这一点的想法是做一系列的拓扑排序来获得一种感觉。特别是，您可以随机地进行第一次拓扑排序。第二种拓扑排序，你试图使尽可能不同，在每一种选择，选择元素的排名最高的时候。第三种拓扑排序，您选择的元素在前一种排序中的级别之和尽可能大。诸若此类。做这个20倍左右。

现在，对于任何一对元素，我们只需看看它们在我们的类型中不一致的频率，就可以估计出一个元素比另一个元素更大的概率。我们可以用以前的公式把它转化为期望熵。

因此，我们以排序中最大秩与最小秩之间最大差的元素开始比较集。

第二个元素是与第一个元素具有最高熵的元素，在排序中，它的最小和最大秩之间的差别最大。

第三种是熵和前两种熵之和是最大的，也是以同样的方式打破联系的。

当然，算法所遵循的确切逻辑是随机的。实际上，您正在根据所找到的比较集执行O(k^2 n)工作。但它的平均收尾会令人惊讶地少一些比较集。

我没有证据，但我怀疑你平均只需要理论上最优的O(log(n!) / log(k!)) = O(n log(n) / (k log(k)))比较。对于k=2，我进一步怀疑它会给出一个比合并排序更有效的解决方案。

Answer 2

在每一轮中，您将对floor(X/Y)批的Y元素和一批X mod Y元素进行排序。

假设为了简单起见，输入是作为一个数组A[1...X]提供的。在第一轮，分批将是A[1...Y], A[Y+1...2Y], ..., A[(floor(X/Y)-1)Y+1...floor(X/Y)Y], A[floor(X/Y)Y+1...X]。在第二轮中，将这些范围按Y/2 places右移(如果您愿意，可以使用环绕，不过为了简单起见，我将简单地假设在偶数迭代中只保留第一个Y/2元素)。因此，范围可以是A[Y/2+1...3Y/2], A[3Y/2+1...5Y/2], etc.。下一轮将重复第一轮的范围，然后将重复第二轮的范围，以此类推。在最坏的情况下，需要多少次迭代才能保证一个完整排序的列表？在最坏的情况下，最大值元素必须从开始迁移到末尾，并且由于一个元素迁移一个完整的奇数迭代部分(参见下面)需要两次迭代，所以它总需要2*ceiling(X/Y)迭代才能到达前面的元素。

示例：

X=11
Y=3
A = [7, 2, 4, 5, 2, 1, 6, 2, 3, 5, 6]
    [7,2,4] [5,2,1] [6,2,3] [5,6] => [2,4,7] [1,2,5] [2,3,6] [5,6]
    2 [4,7,1] [2,5,2] [3,6,5] [6] => 2 [1,4,7] [2,2,5] [3,5,6] [6]
    [2,1,4] [7,2,2] [5,3,5] [6,6] => [1,2,4] [2,2,7] [3,5,5] [6,6]
    1 [2,4,2] [2,7,3] [5,5,6] [6] => 1 [2,2,4] [2,3,7] [5,5,6] [6]
    [1,2,2] [4,2,3] [7,5,5] [6,6] => [1,2,2] [2,3,4] [5,5,7] [6,6]
    1 [2,2,2] [3,4,5] [5,7,6] [6] => 1 [2,2,2] [3,4,5] [5,6,7] [6]
    [1,2,2] [2,3,4] [5,5,6] [7,6] => [1,2,2] [2,3,4] [5,5,6] [6,7]
    1 [2,2,2] [3,4,5] [5,6,6] [7] => no change, termination condition

这可能有点傻，但如果您有一种高效的方法来对小组进行排序，并且有大量的并行性可用，这可能是非常巧妙的。