cha*_*ies 5 sorting algorithm robust noise time-complexity
我想n用比较排序对项目列表进行排序。但是，该算法进行的比较之一将与它应该的情况相反。具体来说，有一对项目的比较器函数始终给出错误的结果。
什么是n*log(n)对这种错误比较具有鲁棒性的有效排序算法？健壮，我的意思是每个项目都k与它的真实位置相差最多点，对于一些相当小的k.
如果可能的话，我希望它在最坏的情况下是稳健的（对抗性选择的错误比较），但我会在平均情况下满足于稳健。
一个示例稳健算法（效率不高）是进行所有n*(n-1)/2成对比较，并根据他们赢得的比较次数来放置每个项目。然后，无论对手进行什么比较，每个项目索引都不会超过k=1。
非鲁棒算法的一个例子是快速排序，因为对手可以选择最大的项目位于第一个枢轴的错误一侧，使其平均n/2偏离其正确索引。
TL;DR：可以修改快速排序以获得以下保证：在（预期）时间 O(n log n) 内，我们可以执行以下操作之一，具体取决于翻转哪个比较。
这保证了最大位移为 2，这在理论上尽可能好。
我仔细考虑了这个问题几个小时，我所做的一切都与锦标赛有关。
我想首先尝试将问题重新定义如下。如果您有一组 n 个项目并且您知道它们之间比较的“真实”结果，您可以将该结果表示为一个有向图，每个项目一个节点，边指示一个项目的比较小于另一个项目。这种类型的有向图称为“锦标赛”，因为您可以将其视为对循环赛的结果进行编码，其中每个玩家与其他玩家进行比赛。
在诚实比较器的情况下，我们的锦标赛将是非循环的，特别是它将具有以下关键属性：每个出度 0, 1, 2, ..., n - 1 恰好有一个节点。这里的想法是最小元素的出度为 n - 1（比其他所有元素都小），而最大元素的出度为 0（比其他元素都大）。事实上，有一个定理是当且仅当锦标赛中的每个节点都有不同的出度时，锦标赛是非循环的。另一个有用的事实：在非循环锦标赛中，当且仅当 outdeg(U) > outdeg(V) 存在从 U 到 V 的边缘。
在“不诚实的比较器”的情况下，我们基本上从非循环锦标赛开始，然后翻转单个边缘。您的问题是关于基于此比较器进行近似排序的，但我想退后一步并提出一个不同的问题，我认为然后可以用它来更准确地回答您的问题。在什么情况下你能找出哪条边被翻转了？如果我们能做到这一点，那么我们可以做得比近似排序更好——我们可以“解开”边缘并完美排序。另一方面，在哪些情况下你无法弄清楚哪条边被翻转，当发生这种情况时，我们最终离排序还有多远？这对应于必须进行近似排序，因为我们无法恢复原始排序。
这是一个有用的事实：
定理：从一个非循环锦标赛开始并翻转一条边。然后，当且仅当翻转边的两个端点的出度最初相差至少 3 时，才有可能确定哪条边被翻转。
为了证明这一点，我们将展示两个方向的含义。
首先，假设我们在出度相差 1 的两个节点 X 和 Y 之间翻转一条边。当我们完成后，我们剩下一个锦标赛，其中所有节点都有不同的出度（所有其他节点的出度不变，如果我们翻转边（X，Y），那么 X 和 Y 交换出度，因为一个上升了一点一点地下降）。我们现在还有另一场非循环锦标赛。尤其是，我们无法确定我们翻转了哪条边，因为我们也可以翻转出度相差 1 的任何一对节点之间的任何边。
接下来，假设我们在节点 X 和 Y 之间翻转一条边，其中 outdeg(X) = k+1 和 outdeg(Y) = k-1。我们现在有 outdeg(X) = k = outdeg(Y)，并且从其他地方开始，一定也有一些具有出度 k 的节点 Z。所以在这一点上，我们有三个出度为 k 的节点（即 X、Y 和 Z），并且我们知道我们必须翻转它们之间的三个边之一。但我们无法分辨它是哪一个。具体来说，翻转 XY 边缘、XZ 边缘或 YZ 边缘都会返回非循环锦标赛。因此，在这种情况下，无法撤消转换。这意味着我们从这个比较器获得的任何排序顺序都会使这两个项目不合适，因此我们的最大距离至少为 1。
对于这种特殊情况的一个重要说明：这对应于比较器创建一个包含节点 X、Y 和 Z 的循环的锦标赛。具体来说，它将采用 X、Z、Y、X 的形式。问题是我们无法判断原始排序是 (X, Z, Y) 还是 (Z, Y, X) 或 (Y, X, Z)，因此我们的最大距离至少为 2。
最后，假设我们有两个节点 X 和 Y 并在 outdeg(X) = k、outdeg(Y) = m 和 k 的情况下翻转边 XY ？m + 3。我们现在剩下一个锦标赛，其中两个节点的出度为 k - 1，两个节点的出度为 m + 1。但是在这四个节点中，可以保证只有一对可以翻转回来产生一个非循环的比赛。一种查看方式：取现在具有重复出度的四个节点；将它们称为 X 和 Y（如上所述）以及 W 和 Z，假设我们有循环 X、W、Z、Y、X，其中与原始翻转的唯一边是 (Y, X)。这个周期会是什么样子？好吧，因为 (X, W), (W, Z), 和 (Z, Y) 是锦标赛中没有翻转的边，所以在最初的锦标赛中我们有 outdeg(X) > outdeg(W) > outdeg (Z) > outdeg(Y)。这意味着我们必须让 X 和 W 在新图中的出度为 k - 1，而 Z 和 Y 在新图中的出度为 m + 1。因此，仅将边从 Y 翻转到 X 会将度数-(k-1) 个节点之一的度数增加回 k，同时还将度数-(m+1) 个节点之一的度数降低到 m .
总结：
定理：有故障的比较器要么
- 表现得像一个真正的比较器，在这种情况下，我们交换了原始序列中的两个相邻元素，我们永远不会知道哪个。
- 恰好有一个长度为 3 的元素的循环，其原始排序永远无法知道，或
- 有一个长度为 4 的循环，在这种情况下，我们可以确定哪个比较是反向的。
考虑到这一点，按以下方式重新构建您的问题似乎是合理的：
目标：设计一个算法，在时间为 O(n log n) 的情况下，对包含 n 个元素的列表执行以下操作之一，给出一个错误的比较器，该比较器在将两个固定元素 X 和 Y 相互比较时返回错误结果：
- 对列表进行完美排序。
- 对列表进行完美排序，除非交换了两个相邻的项目。
- 对列表进行完美排序，但排列的三个相邻项目除外。
这是一种可能的算法，它在基于快速排序的预期 O(n log n) 时间内完成此操作。基本思想如下：我们或多或少地运行一个常规的快速排序，在每个时间点检查我们是否找到了一个三角形。如果不是，那么我们要么是情况（1），要么是情况（2）。如果我们确实找到了一个三角形，我们看看是否可以确定哪个比较被颠倒了。如果可以，那么我们重新运行快速排序，只是在这种损坏的情况下我们“修复”了比较器。如果我们不能，那么我们就在情况（3）中，像往常一样完成快速排序。
我们将用于检测三角形的特定技术是这样工作的。从常规的普通快速排序开始：选择一个主元，将数组划分为小于主元和大于主元的部分，然后递归排序两个较小的子数组。然而，在这样做之后，我们做了一个额外的步骤：假设我们正在排序的子数组中有三个或更多元素，查看主元 p 和它前后的元素（将那些 s、p、g 称为“更小”、“枢轴”和“更大”）。然后如果比较器说 s < p < g < s，我们就找到了一个三角形。事实上，我们有更强大的东西。
假设在快速排序比较器中的某个时刻确实比较了 X 和 Y，即不匹配的项目。我们假设 X < Y，但是比较器错误地报告 Y < X。在快速排序中比较两个项目的唯一方法是，当另一个项目在当前子数组中时，其中一个项目是否是枢轴元素. 在不失一般性的情况下，让我们假设 X 是枢轴，并将 Y 与它进行比较。
应该怎么做这里发生的情况是，假设比较器是诚实的，会发现 Y 大于 X，因此将被放入“更大”的子数组中。但是因为比较器是一个说谎的骗子，所以 Y 被放置在“较小”的子数组中。如果我们然后递归地对“较小”的子数组和“较大”的子数组进行排序，请考虑 Y 最终会在哪里。它在“较小”的子数组中，但实际上比 X 大，这意味着它将比“较小”子数组中的所有内容都大。因此，Y 将出现在 X 之前。现在，查看“更大”子数组中的项目。有两种选择。第一个是在“真实”排序中，X 和 Y 之间至少有一个值。然后该值将出现在“更大”中 子数组，因为它比 X 大，特别是“较大”子数组的第一个元素将比 Y 小。这意味着 Y，然后是 X，然后在排序后紧跟在 X 之后的项目将形成一个三角形。另一种选择是 X 和 Y 在真正的排序中是相邻的，这种情况我们永远不会发现（如上所述）。这与上述见解相结合，意味着
定理：假设我们运行快速排序，在对左右子数组进行递归排序后，我们查看由枢轴、它前面的项和它后面的项组成的三个项，看它们是否形成一个三角形。那么如果这个算法检测到一个三角形，那么就存在一个三角形。此外，如果此算法未检测到三角形，则 (1) 不存在三角形或 (2) 三角形确实存在，但比较器从未应用于坏对 (X, Y)，因此排序顺序是正确的.
说了这么多，完成了所有这些，我们可以陈述完整的算法，在预期的 O(n log n) 时间内，尽可能对数组进行排序。
function modifiedQuicksort(array, comparator):
if array has length 0 or 1, return.
pick a random pivot element from the array.
use the comparator to form subarrays smaller and greater based on
how elements compare against the pivot.
recursively apply modifiedQuicksort to those two arrays.
if the comparator finds a triangle formed from the last element of
smaller, the pivot, and the first element of greater, report those
three items as a triangle.
return smaller, pivot, greater.
function sortAsBestWeCan(array, comparator):
run modifiedQuicksort(array, comparator)
if it didn't report a triangle, return the result of the call.
otherwise, it reported a triangle A, B, C.
for each other item D:
if comparator(A, D) and comparator(D, B) or
comparator(B, D) and comparator(D, C) or
comparator(C, D) and comparator(D, A):
you have found a 4-cycle from A, B, C, and D.
detect which comparison is reversed.
use that knowledge plus the comparator and your favorite
O(n log n)-time sorting algorithm to perfectly sort
the input array.
otherwise, those three items are the only triangle, and the
array is sorted as well as it can be. return it.
我想我已经想出了一个解决方案。
首先，使用您想要的任何合适的排序算法（例如快速排序）进行第一遍，这在最坏的情况下应该只产生一个与应有位置相距甚远的项目。
h然后，选择至少为 5 的宽度。
for i from 0 to n-hh，我们查看位于 的项目组i, i+1, ..., i+h-1。我们h*(h-1)/2对该组中的所有成对比较进行比较，并根据谁赢得最多的比较重新排列它们。然后我们递增i并移动到下一组。
之后，我们做同样的事情，但是从i=n-h到倒退i=0。
这两个额外的通道将使移位的项目向上冒泡/向下冒泡到正确的区域，并使用一组中的额外比较h来覆盖错误的单一比较。
最终的比较次数为O(n*log(n)) + n*h*(h-1)/2。不知道你能做得更好多少。
（我认为）这种方法也适用于不止一次错误的比较。您需要做的就是确保它h足够大以覆盖那些错误的比较。