QuickSort和Hoare分区

Question

我很难将QuickSort与Hoare分区转换为C代码,但无法找到原因.我正在使用的代码如下所示:

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;
    }
}

此外,我真的不明白为什么HoarePartition工作.有人可以解释它为什么有效,或者至少把我链接到一篇文章吗？

我已经看到了分区算法的逐步完成,但我没有直观的感觉.在我的代码中,它似乎甚至没有用.例如,给定数组

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

它将使用数据透视表13,但最终会使用数组

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

并将返回j哪个a[j] = 11.我认为从那个点开始并且前进的数组应该具有比枢轴更大的值,这应该是真的,但是这不是真的,因为11 <13.

这是Hoare分区的伪代码(来自CLRS,第二版),如果这很有用:

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 

谢谢!

编辑:

这个问题的正确C代码将最终成为:

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;
    }
}

Answer 1

回答"为什么Hoare分区工作？"的问题:

让我们将数组中的值简化为三种: L值(小于透视值的值),E值(等于透视值)和G值(大于透视值的值).

我们还将为数组中的一个位置指定一个特殊名称; 我们将这个位置称为s,它是程序结束时j指针所在的位置.我们是否事先知道哪个位置小号是什么？不,但我们知道某个位置会符合该描述.

使用这些术语,我们可以用稍微不同的术语表达分区过程的目标:它是将单个数组拆分成两个较小的子数组,这些子数组不会相互错误排序.如果满足以下条件,则满足"未错误排序"的要求:

1. 从阵列的左端到包含s的"低"子阵列不包含G值.
2. 在s之后立即开始并继续到右端的"高"子阵列不包含L值.

这才是我们真正需要做的.我们甚至不用担心E值在任何给定的传球中都会结束.只要每次传递使子阵列相对于彼此正确,后来的传递将处理任何子阵列内存在的任何障碍.

所以,现在让我们来解决从对方的问题:如何划分方法确保没有摹价值观小号或它的左侧,并没有大号值的权小号？

好吧," s右边的值集合"与" j指针到达s之前移动的单元格集"相同.和"该组值的左侧,并且包括小号 "是相同的"的设定值的,所述我指针之前移过Ĵ到达小号 ".

这意味着在循环的某些迭代中,任何放错位置的值都将位于我们的两个指针中.(为方便起见,我们说这是Ĵ指针在指向大号价值,但它的工作原理完全为同一我指针在指向摹值).该会在哪里我指针,当Ĵ指针是一个错位的价值？我们知道它将是:

1. 在"低"子阵列中的某个位置,L值可以没有问题;
2. 指向一个值为E或G值的值,可以轻松替换j指针下的L值.(如果它不是E或G值,它就不会停在那里.)

请注意,有时i和j指针实际上都会停止在E值上.发生这种情况时,即使不需要,也会切换值.但这并没有造成任何伤害; 我们之前说过,E值的放置不会导致子阵列之间的错误排序.

总而言之,Hoare分区的工作原理是:

1. 它将一个数组分成较小的子数组,这些子数组相对于彼此没有错误排序;
2. 如果你继续这样做并递归地对子数组进行排序,那么最终将没有任何内容未被排序.

Answer 2

我相信这段代码存在两个问题.对于初学者来说,在你的Quicksort功能中,我想你想重新排序

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

所以你有这样的:

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

但是,你应该做的比这更多; 特别是这应该读

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

原因是如果您尝试分区的范围大小为零或一个,则Hoare分区无法正常工作.在我的CLRS版本中,这里没有提到; 我不得不去书的勘误页找到这个.这几乎可以肯定是"访问超出范围"错误所遇到的问题的原因,因为在不变的情况下,您可以直接从阵列运行!

至于Hoare分区的分析,我建议首先手动追踪它.还有一个更详细的分析在这里.直观地说,它通过从范围的两端向另一端增长两个范围来工作 - 一个在左侧包含小于枢轴的元素,一个在右侧包含比枢轴大的元素.这可以稍微修改以产生Bentley-McIlroy分区算法(在链接中引用),该算法可以很好地扩展以处理相等的密钥.

希望这可以帮助!