Hoare分区算法说明 [英] Explanation of Hoare Partitioning algorithm

问题描述

根据很多网站给出的伪代码，我写了这个 Hoare 分区算法，它需要一个数组，子数组的开始和结束索引基于给定的支点.它工作正常，但有人可以解释逻辑，它是如何做的吗?代码如下:

As per the pseudo-code given in many websites, I have written this Hoare partitioning algorithm, which takes an array, the start and end indexes of the sub-array to be partitioned based on the pivot given. It works fine, but can somebody explain the logic, how it does what it does? Here' the code:

def hoare(arr,start,end):
     pivot = 4
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     return j    

分区还有另一种变体，Lomuto 算法.它做了类似的事情，尽管因为我首先不理解 Hoare 算法，所以我无法发现差异.谁能解释一下算法中发生了什么，在哪种情况下哪个性能更好?

There's another variant of the partitioning, the Lomuto algorithm. It does something similar, although since I don't understand the Hoare algorithm in the first place, I can't spot the difference. Can anybody explain what's going on in the algorithm, and which one gives a better performance in which case?

推荐答案

我建议使用一副纸牌和两个棋子/硬币来表示 i 和 j.基本上，该算法同时完成了这两件事:

I'd suggest simulating this using a deck of cards and two pawns / coins to represent i and j. Basically, the algorithm accomplishes these two things, simultaneously:

• 找到哪里应该拆分数组，以便在此位置的左侧和右侧拥有正确数量的桶".这是通过 i 和 j 的值在分区的中间"相遇来完成的.
• 将数组元素移动到中间的左侧或右侧，具体取决于它们是小于还是大于枢轴.

• Find where the array should be split up to have the correct amount of "buckets" to the left and to the right of this position. This is done by the values of i and j meeting in the "middle" of the partition.
• Move the array elements to either left, or the right of the middle, depending on whether they're lesser and greater than the pivot.

这意味着在任何时候，i 要么在它的中间，要么在它的左边.j 的情况正好相反.知道了这一点，就可以看到 while 循环所做的是找到一个位于中间左侧但应该在右侧的元素，反之亦然.也就是说，找到 两个 元素在错误的一半.然后将它们交换.

This means that at any time, i is either at the middle or left of it. The converse is true for j. Knowing this, one can see that what the while loops do is find an element that's to the left of the middle but should be on the right, and vice versa. That is, find two elements that are in the wrong half. These are then swapped.

当 i 和 j 在中间相遇时，在左边你有被 while 跳过的元素，因为它们比 pivot 小；或从另一侧交换的元素，因此也小于 pivot.(对于中间右侧的元素，反之亦然.)

When i and j meet in the middle, to the left you have either elements that were skipped by the while, because they're smaller than pivot; or elements that were swapped from the other side, and are thus also smaller than pivot. (Vice versa for the elements right of the middle.)

一个可能的混淆源是从零开始的数组索引可以被认为指向一个元素，或者指向两个元素之间的.例如.索引 0 基本上意味着在‘零’和数组中的第一个元素之间"，当你访问一个元素时，你取跟随这个位置- 使 array[0] 的结果直观地成为数组的第一个元素.

A possible source of confusion is that a zero-based array index can be thought to either point at an element, or to point between two elements. E.g. the index 0 basically means "between the 'zeroth' and the first element in the array", and when you're accessing an element, you take the one following this position - making array[0] result in what's intuitively the first element of the array.

这篇关于Hoare分区算法说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！