这个奇怪的排序算法是什么? [英] What is this odd sorting algorithm?

问题描述

一些答案原来有这种排序算法:

Some answer originally had this sorting algorithm:

for i from 0 to n-1:
    for j from 0 to n-1:
        if A[j] > A[i]:
            swap A[i] and A[j]

注意 i 和 j 都是完整的范围，因此 j 可以比 i，因此它可以使配对顺序正确和错误(而且它实际上确实做到了！).我认为这是一个错误(作者后来称之为错误)并且这会使数组混乱，但它似乎确实排序正确.不过，原因并不明显.但是代码的简单性(全范围，没有冒泡排序中的+1)使它变得有趣.

Note that both i and j go the full range and thus j can be both larger and smaller than i, so it can make pairs both correct and wrong order (and it actually does do both!). I thought that's a mistake (and the author later called it that) and that this would jumble the array, but it does appear to sort correctly. It's not obvious why, though. But the code simplicity (going full ranges, and no +1 as in bubble sort) makes it interesting.

正确吗?如果是这样，它为什么有效?它有名字吗?

带测试的 Python 实现:

Python implementation with testing:

from random import shuffle

for _ in range(3):
    n = 20
    A = list(range(n))
    shuffle(A)
    print('before:', A)

    for i in range(n):
        for j in range(n):
            if A[j] > A[i]:
                A[i], A[j] = A[j], A[i]

    print('after: ', A, '\n')

示例输出(在线试用！):

before: [9, 14, 8, 12, 16, 19, 2, 1, 10, 11, 18, 4, 15, 3, 6, 17, 7, 0, 5, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [5, 1, 18, 10, 19, 14, 17, 7, 12, 16, 2, 0, 6, 8, 9, 11, 4, 3, 15, 13]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

before: [11, 15, 7, 14, 0, 2, 9, 4, 13, 17, 8, 10, 1, 12, 6, 16, 18, 3, 5, 19]
after:  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 

有人指出了一篇关于该算法的非常不错的全新论文.澄清一下:我们没有血缘关系，纯属巧合.据我所知，它是提交给 arXiv 之前 这个答案引发了我的问题和 发布 arXiv 之后 我的问题.

Someone pointed out a very nice brand new paper about this algorithm. Just to clarify: We're unrelated, it's a coincidence. As far as I can tell it was submitted to arXiv before that answer that sparked my question and published by arXiv after my question.

推荐答案

为了证明它是正确的，你必须找到某种不变量.在循环的每一次传递中都是正确的.

To prove that it's correct, you have to find some sort of invariant. Something that's true during every pass of the loop.

看看它，在内循环的第一遍之后，列表的最大元素实际上将位于第一个位置.

Looking at it, after the very first pass of the inner loop, the largest element of the list will actually be in the first position.

现在在内循环的第二遍中，i = 1，第一次比较是在 i = 1 和 j = 0.所以，最大的元素在位置 0，经过这次比较，它会被交换到位置 1.

Now in the second pass of the inner loop, i = 1, and the very first comparison is between i = 1 and j = 0. So, the largest element was in position 0, and after this comparison, it will be swapped to position 1.

一般来说，那么不难看出，在外循环的每一步之后，最大的元素都会向右移动一个.所以在完整的步骤之后，我们知道至少最大的元素会在正确的位置.

In general, then it's not hard to see that after each step of the outer loop, the largest element will have moved one to the right. So after the full steps, we know at least the largest element will be in the correct position.

剩下的呢?假设第二大元素位于当前循环的 i 位置.根据前面的讨论，我们知道 最大 元素位于 i-1 位置.计数器 j 从 0 开始.所以现在我们正在寻找第一个 A[j] 使得它是 A[j] >A[i].好吧，A[i] 是第二大元素，所以第一次发生在 j = i-1 时，在第一大元素.因此，它们相邻并被交换，现在处于正确"位置.命令.现在 A[i] 再次指向最大的元素，因此对于内部循环的其余部分，不再执行交换.

What about all the rest? Let's say the second-largest element sits at position i of the current loop. We know that the largest element sits at position i-1 as per the previous discussion. Counter j starts at 0. So now we're looking for the first A[j] such that it's A[j] > A[i]. Well, the A[i] is the second largest element, so the first time that happens is when j = i-1, at the first largest element. Thus, they're adjacent and get swapped, and are now in the "right" order. Now A[i] again points to the largest element, and hence for the rest of the inner loop no more swaps are performed.

所以我们可以说:一旦外循环索引移过第二大元素的位置，第二大和第一大元素的顺序就会正确.在外循环的每次迭代中，它们现在将一起向上滑动，因此我们知道在算法结束时，第一大和第二大元素都将处于正确位置.

So we can say: Once the outer loop index has moved past the location of the second largest element, the second and first largest elements will be in the right order. They will now slide up together, in every iteration of the outer loop, so we know that at the end of the algorithm both the first and second-largest elements will be in the right position.

第三大元素呢?好吧，我们可以再次使用相同的逻辑:一旦外循环计数器 i 位于第三大元素的位置，它将被交换，使其刚好低于第二大元素元素(如果我们已经找到了那个！)或者在第一个最大元素下方.

What about the third-largest element? Well, we can use the same logic again: Once the outer loop counter i is at the position of the third-largest element, it'll be swapped such that it'll be just below the second largest element (if we have found that one already!) or otherwise just below the first largest element.

啊.现在我们有了我们的不变量:在外循环的 k 次迭代之后，k 长度的元素序列，在位置 k-1 结束，将按排序顺序:

Ah. And here we now have our invariant: After k iterations of the outer loop, the k-length sequence of elements, ending at position k-1, will be in sorted order:

在第 1 次迭代之后，位置 0 处的长度为 1 的序列将按正确顺序排列.这是微不足道的.

After the 1st iteration, the 1-length sequence, at position 0, will be in the correct order. That's trivial.

第二次迭代后，我们知道最大的元素在位置1，所以显然序列A[0],A[1]的顺序是正确的.

After the 2nd iteration, we know the largest element is at position 1, so obviously the sequence A[0], A[1] is in the correct order.

现在假设我们在步骤 k，所以直到位置 k-1 的所有元素都将是有序的.现在i = k，我们遍历j.这样做基本上是找到新元素需要插入现有排序序列的位置，以便正确排序.一旦发生这种情况，其余元素就会冒泡".到目前为止，最大的元素位于位置 i = k 并且没有进一步的交换发生.

Now let's assume we're at step k, so all the elements up to position k-1 will be in order. Now i = k and we iterate over j. What this does is basically find the position at which the new element needs to be slotted into the existing sorted sequence so that it'll be properly sorted. Once that happens, the rest of the elements "bubble one up" until now the largest element sits at position i = k and no further swaps happen.

因此最后在步骤 N 的末尾，直到位置 N-1 的所有元素都处于正确的顺序，QED.

Thus finally at the end of step N, all the elements up to position N-1 are in the correct order, QED.

这篇关于这个奇怪的排序算法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！