用谎言排序

Question

问题:考虑排序n个项目的问题，其中比较oracle在执行算法时最多允许躺一次。复杂性是根据所使用的比较(oracle 咨询)的数量来衡量的。展示如何仅使用 nlgn +O(n) 比较对这个模型中的 n 个项目进行排序，给出您的算法和正确性证明。

我有什么:

到目前为止，我最好的解决方案非常简陋。我基本上是在实现一种形式的合并排序，唯一的区别是，在与合并进行比较时，我比较了两次(因为如果存在不一致，oracle 只能说谎一次，我将进行第三次比较，但这只能发生一次)。

我知道合并有 lg(n) 个级别，并且由于我有 n 个元素，因此我将进行的最大比较量是 2nlg(n)+1。然而，这是一个相当粗略的上限，因为我知道两个长度为 m 和 p 的数组的合并需要 m+p-1 比较(而不是 m+p)。

为简单起见，如果我假设数组长度是 2 的幂，我有 m=p，我总共得到 n-1 次合并。所以我可以从 2nlg(n)+1 中减去 2(n-1) 得到 2nlg(n) - 2n - 1 个比较。

不完全是我正在寻找的答案。我认为我的做法是错误的(我认为我没有必要每次合并时都进行两次比较..)，如果有人能将我推向正确的方向，我将不胜感激!

干杯，

萨沙

Answer 1

我的解决方案:

(假设我为了语言的简单性而按递增顺序对数字进行排序)。

1)我像往常一样执行 MergeSort(我的数组中最多有一个错误)

2)我遍历数组，将每个索引与下一个索引比较两次(也许第三次
一次如果比较结果不一致)

3)如果A[i] > A[i+1](被oracle确认两次)，我发现了我的错误，切换A[i+1]和A[i]，检查A[i+1] >A[i+2]，如果是这种情况，向上数组比较 A[i+1] 和 A[i+2] 两次(最坏情况)，依此类推(直到 i 达到 n-2)。如果 A[i+1]>A[i+2]，则在每个阶段切换 A[i+1] 和 A[i+2]。如果 A[i+1]<=A[i+2]，则将 A[i] 与 A[i-1] 比较两次(最坏情况)，以此类推(直到 i 达到 0)。如果 A[i]>A[i-1]，则在每个阶段切换 A[i] 和 A[i-1]。

第 1 步将导致少于 nlgn 次比较，第 2 步和第 3 步最多为 4n+1 次比较。

当然，所有这些都需要正式化，但我认为这是基本思想。

如果我遗漏了什么或在这里完全弄错了，请不要犹豫让我知道。

谢谢，

萨沙