Hoare分区不起作用? [英] Hoare partition doesn't work?

问题描述

我一直在尝试实现Hoare分区方法，但是我和计算机似乎都无法理解它，因为它是用Cormen和Wikipedia编写的.两种资源中的算法如下:

I have been trying to implement the Hoare partitioning method, but neither I, nor the computer can't seem to understand it as it is written in Cormen and Wikipedia. The algorithm in both sources looks like this:

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            j := j - 1
        while A[j] > pivot
        do
            i := i + 1
        while A[i] < pivot
        if i < j then
            swap A[i] with A[j]
        else
            return j

对于以下数组:9 3 11 55 4，使用上述函数对它进行分区后，将如下所示:4 3 11 55 9，并且枢轴索引为2，这完全是错误的.首先，将交换9和4，所以我将成为2，而j将成为4.但是，在下一次迭代期间，由于do while循环，将跳过9并且将再也不会交换.我的想法有问题吗?(我认为我在C ++中的实现没有任何错误)

For the following array: 9 3 11 55 4 , after partitioning it with the above function, it will look like this: 4 3 11 55 9 and the pivot index will be 2 which is completely false. Firstly, 9 and 4 will be swapped, so i will become 2 and j will become 4. But, during the next iteration, because of the do while loop, 9 will be skipped and will never ever be swapped again. Is there a problem with my thinking? (I think that my implementation in C++ doesn't have any mistakes)

#include <iostream>
using namespace std;
int a[100];
int partitie(int st, int dr){
    int i,j,x;
    x=a[st];
    i=st-1;
    j=dr+1;
    while(true){
        do{
            j--;
        }while(a[j]>x);
        do{
            i++;
        }while(a[i]<x);
        if(i<j) swap(a[i],a[j]);
        else return j;
    }
}
int main() {
    int i,n;
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    cout<<partitie(1,n)<<endl;
    for(i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

推荐答案

您需要使用正确的quicksort例程，因为Hoare将数组拆分为左侧和右侧，而Lomuto则将数组拆分为左侧，旋转，正确的部分.

You need to use the correct quicksort routine, since Hoare splits an array into left part and right part, unlike Lomuto which splits an array into left part, pivot, right part.

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p)        // not quicksort(A, lo, p-1)
        quicksort(A, p + 1, hi)

还在中间选择一个枢轴，这意味着已经排序或反向排序的数组可以快速排序，而不是最坏的情况:

also choosing a pivot in the middle means that an already sorted or reverse sorted array is sorted quickly as opposed to being worst case:

    pivot := A[lo+(hi-lo)/2]  // or := A[(lo+hi)/2] if overflow not an issue

仍然存在最坏的情况，但是至少处理了简单的情况.中位数3会稍慢一些，但会减少最坏情况下的模式数量:

There would still be worst case patterns, but at least the simple ones are handled. Median of 3 is a bit slower, but reduces the number of worst case patterns:

    md = lo + (hi-lo)/2
    if (A[lo] > A[hi])
        swap(A[lo], A[hi])
    if (A[lo] > A[md])
        swap(A[lo], A[md])
    if (A[md] > A[hi])
        swap(A[md], A[hi])
    pivot := a[md]

也许您正在寻找的是快速选择来找到第k个元素，其中k =数组大小/2.这类似于快速排序，但是它仅以递归方式搜索包含第k个元素的数组的左侧或右侧部分.Wiki文章:

Perhaps what you're looking for is quick select to find the kth element where k = array size / 2. It's similar to quick sort, but it only recursively searches the left or right part of the array that contains the kth element. Wiki article:

http://en.wikipedia.org/wiki/Quickselect

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