快速排序特例 - 似乎是从K＆放一个错误的算法; R [英] quicksort special case - seems to be a faulty algorithm from K&R

问题描述

我的理解，从K＆安培快速排序算法（简化版本没有指针）的一个问题; R。已经有由Dave宝洁这里<提供一个完整的解释href=\"http://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion\">explanation.
不过，我注意到，与微微一变字符串开始，我们可以在for循环的循环很多没有获得交换。
首先在code：

I have a problem understanding quicksort algorithm (the simplified version without pointers) from K&R. There is already a thorough explanation provided by Dave Gamble here explanation. However I noticed that by starting with a slightly changed string we can obtain no swaps during many loops of the for loop. Firstly the code:

void qsort(int v[], int left, int right)
{
    int i, last;

    void swap(int v[], int i, int j);

    if (left >= right) /* do nothing if array contains */
            return;         /* fewer than two elements */
    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                    /* to v[0] */
    for (i = left + 1; i <= right; i++) /* partition */
            if (v[i] < v[left])
                    swap(v, ++last, i);
    swap(v, left, last);                  /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

演练在我看来：

我们先从CADBE;左边= 0;右= 4; D是枢轴
所以根据算法，我们交换ð用C获得DACBE

we start with CADBE; left=0; right=4; D is the pivot so according to algorithm we swap D with C obtaining DACBE

最后= left = 0的

last = left =0

= 1，如果我（V <一个href=\"http://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion\">1 ＆LT; v [0]），所以我们换v 1用v <一个（因为最后是操作之前递增） href=\"http://stackoverflow.com/questions/1231254/kr-qsort-example-with-pointers-and-arrays-confusion\">1所以没有什么变化，去年= 1，仍然有DACBE;

i = 1 if ( v1 < v[0] ) it is true so we swap v1 (because last is incremented before operation) with v1 so nothing changes, last = 1, still having DACBE;

现在我= 2，如果（V [2] LT; v [0]） - > true，所以我们交换V [2]与V [2]没有再次改变;去年= 2

now i = 2 if ( v[2] < v[0] ) -> true so we swap v[2] with v[2] nothing changed again; last = 2

现在我= 3，如果（V [3]＆LT; v [0]） - （！）> true，所以我们换v [3]用v [3]没有，没有改变，最后= 3

now i = 3 if ( v[3] < v[0] ) -> true so we swap v[3] with v[3] nothing changed AGAIN (!), last = 3

因此​​很明显，什么是错的，算法什么也不做。
您的意见AP preciated非常多。我一定是错的，作者是比我好; d
在此先感谢！

So apparently something is wrong, algorithm does nothing. Your opinions appreciated very much. I must be wrong, authors are better than me ;D Thanks in advance!

推荐答案

循环从进入左+ 1 到和包括的右。当 I = 4 ，测试失败和末页没有得到增加。

The loop goes from left + 1 up to and including right. When i=4, the test fails and last does not get incremented.

然后递归调用排序 BACDE 与左= 0，右= 2 和左= 4，右= 4 。 （这是正确的，当 D 为支点。）

Then the recursive calls sort BACDE with left=0,right=2 and left=4,right=4. (Which is correct when D is the pivot.)

这篇关于快速排序特例 - 似乎是从K＆放一个错误的算法; R的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！