3

K&R のクイックソート アルゴリズム (ポインターのない単純化されたバージョン) を理解するのに問題があります。Dave Gamble による詳細な説明がすでにあります。しかし、わずかに変更された文字列から開始すると、for ループの多くのループ中にスワップを取得できないことに気付きました。まずコード：

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 はピボットであるため、アルゴリズムに従って D を C と交換し、DACBE を取得します。

最後 = 左 = 0

i = 1 if ( v 1 < v[0] ) は真なので、v 1 を v 1 と交換します(操作の前に last がインクリメントされるため) 。

ここで i = 2 if ( v[2] < v[0] ) -> true なので、v[2] を v[2] と交換します。最後 = 2

今 i = 3 if ( v[3] < v[0] ) -> true なので、v[3] を v[3] と交換します 再び (!)、last = 3 何も変わりません

どうやら何かがおかしいので、アルゴリズムは何もしません。貴重なご意見、ありがとうございました。私は間違っているに違いありません、著者は私よりも優れています;D 事前に感謝します!

4

2 に答える 2

3

ループは からleft + 1まで続き rightます。の場合i=4、テストは失敗し、lastインクリメントされません。

次に、再帰呼び出しは and でソートさBACDEれます。（ピボットの場合は正しいです。）left=0,right=2left=4,right=4D

于 2012-08-13T17:29:25.773 に答える
2

たまたま、入力サブ配列が(よりも小さく、 よりも大きい)ACBEによって既に分割されているため、分割サイクルが値を物理的に交換しないことは驚くことではありません。DACBDED

実際には、「何もしない」というのは正しくありません。入力データに追加の並べ替えが必要ないため、サイクル内で並べ替えは行われません。しかし、それでも 1 つのことを行います: それは、小さな要素がどこで終わり、大きな要素が始まるかを示す の値をlast見つけACBEます。サイクルは で終了します。これは、さらなる再帰ステップの分割ポイントです。ACBElast == 3

于 2012-08-13T17:29:10.733 に答える