快速排序和霍尔分区 [英] QuickSort and Hoare Partition

问题描述

我有一个很难翻译的快速排序与霍尔划分为C code，并不能找出原因。在code我用如下：

 无效快速排序（INT A []，诠释开始，诠释完）{
    INT Q = HoarePartition（一，开始，结束）;
    如果（完＆LT; =启动）的回报;
    快速排序（A，Q + 1，结束）;
    快速排序（A，开始，Q）;
}

INT HoarePartition（INT A []，INT磷，INT读）{
    INT X = A [P]，I =对 -  1，J = R;
    而（1）{
        做j--;而（一[J] GT; X）;
        做我++;而（一个[1]  - ; x）的;

        如果（ⅰ＆所述; j）条
            交换（安培; A [1]，＆安培;一个[j]的）;
        其他
            复位J;
    }
}
 

另外，我真的不知道为什么 HoarePartition 的作品。有人可以解释为什么它工作，或者至少我链接到一篇文章，说呢？

我已经看到了一步一步的工作，通过分区算法，但我没有一个直观的感受吧。在我的code，它甚至不似乎工作。例如，给定的阵列

  13 19 9 5 12 8 7 4 11 2 6 21
 

这将使用支点13，但最终与数组

  6 2 9 5 12 8 7 4 11 19 21
 

和将返回Ĵ是 A [J] = 11 。我认为这是应该的阵列开始在这一点上，还是今后应该有都比枢轴较大的值，但事实并非如此这里是真实的，因为11＆LT; 13。

下面是伪code代表霍尔分区（从CLRS，第二版），在此情况下，是非常有用的：

 霍尔-分区（A，P，R）
 进行x←A [P]
     我←对 -  1
     Ĵ←R + 1
 而TRUE
        重复Ĵ←的J  -  1
            直到[J]≤x
    重复一遍，我←I + 1
            直到A [1]≥x
    如果我＆LT; Ĵ
              交换A [1]↔A [J]。
    否则复位J
 

谢谢！

编辑：

右C $ C $下这个问题最终会被：

 无效快速排序（INT A []，诠释开始，诠释完）{
    INT q;
    如果（年底启动2）返回;
    Q = HoarePartition（一，开始，结束）;
    快速排序（A，开始，Q）;
    快速排序（A，Q，端）;
}

INT HoarePartition（INT A []，INT磷，INT读）{
    INT X = A [P]，I =对 -  1，J = R;
    而（1）{
        做j--;而（一[J] GT; X）;
        做我++;而（一个[1]  - ; x）的;
        如果（ⅰ＆所述; j）条
            交换（安培; A [1]，＆安培;一个[j]的）;
        其他
            返回J + 1;
    }
}
 

解决方案

我认为有两个问题code。对于初学者来说，在快速排序的功能，我想你要重新排序的行

  INT Q = HoarePartition（一，开始，结束）;
 如果（完＆LT; =启动）的回报;
 

让你有他们这样的：

 如果（完＆LT; =启动）的回报;
 INT Q = HoarePartition（一，开始，结束）;
 

不过，你应该做的比这还要多;特别是本应读

 如果（结束 - 开始2）回报;
 INT Q = HoarePartition（一，开始，结束）;
 

这样做的原因是，霍尔分区无法正常工作，如果你想分区的范围大小为0或1。在我CLRS版这不是在任何地方提及;我不得不去为 本书的勘误表 找到这个。这是几乎可以肯定你的访问超出范围的错误所遇到的问题的原因，因为与不变破，你可能会遇到马上阵！

至于霍尔划分的分析，我建议通过它只是跟踪用手出发。还有一个更详细的分析 这里 。直观地说，它的工作原理是生长两个范围从朝向彼此的范围内的端部 - 的左侧包含元素比枢轴，一个在右侧包含元素比枢轴较大较小的一个。这可以稍微修改以产生宾利 - 麦克罗伊分割算法（在链接中引用），其很好地扩展来处理相同的密钥。

希望这有助于！

I have a hard time translating quicksort with Hoare partitioning into C code, and can't find out why. The code I'm using is shown below:

void QuickSort(int a[],int start,int end) {
    int q=HoarePartition(a,start,end);
    if (end<=start) return;
    QuickSort(a,q+1,end);
    QuickSort(a,start,q);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);

        if  (i < j)
            swap(&a[i],&a[j]);
        else
            return j;
    }
}

Also, I don't really get why HoarePartition works. Can someone explain why it works, or at least link me to an article that does?

I have seen a step-by-step work-through of the partitioning algorithm, but I don't have an intuitive feel for it. In my code, it doesn't even seem to work. For example, given the array

13 19  9  5 12  8  7  4 11  2  6 21

It will use pivot 13, but end up with the array

 6  2  9  5 12  8  7  4 11 19 21 

And will return j which is a[j] = 11. I thought it was supposed to be true that the array starting at that point and going forward should have values that are all larger than the pivot, but that isn't true here because 11 < 13.

Here's pseudocode for Hoare partitioning (from CLRS, second edition), in case this is useful:

Hoare-Partition (A, p, r)
 x ← A[p]
     i ← p − 1
     j ← r + 1
 while  TRUE
        repeat   j ←  j − 1
            until     A[j] ≤ x
    repeat   i ←  i + 1
            until     A[i] ≥ x
    if  i < j
              exchange  A[i] ↔ A[j]
    else  return   j 

Thanks!

EDIT:

The right C code for this problem will end up being:

void QuickSort(int a[],int start,int end) {
    int q;
    if (end-start<2) return;
    q=HoarePartition(a,start,end);
    QuickSort(a,start,q);
    QuickSort(a,q,end);
}

int HoarePartition (int a[],int p, int r) {
    int x=a[p],i=p-1,j=r;
    while (1) {
        do  j--; while (a[j] > x);
        do  i++; while (a[i] < x);
        if  (i < j) 
            swap(&a[i],&a[j]);
        else 
            return j+1;
    }
}

解决方案

I believe that there are two problems with this code. For starters, in your Quicksort function, I think you want to reorder the lines

 int q=HoarePartition(a,start,end);
 if (end<=start) return;

so that you have them like this:

 if (end<=start) return;
 int q=HoarePartition(a,start,end);

However, you should do even more than this; in particular this should read

 if (end - start < 2) return;
 int q=HoarePartition(a,start,end);

The reason for this is that the Hoare partition fails to work correctly if the range you're trying to partition has size zero or one. In my edition of CLRS this isn't mentioned anywhere; I had to go to the book's errata page to find this. This is almost certainly the cause of the problem you encountered with the "access out of range" error, since with that invariant broken you might run right off the array!

As for an analysis of Hoare partitioning, I would suggest starting off by just tracing through it by hand. There's also a more detailed analysis here. Intuitively, it works by growing two ranges from the ends of the range toward one another - one on the left-hand side containing elements smaller than the pivot and one on the right-hand side containing elements larger than the pivot. This can be slightly modified to produce the Bentley-McIlroy partitioning algorithm (referenced in the link) that scales nicely to handle equal keys.

Hope this helps!

这篇关于快速排序和霍尔分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！