0

次のクイックソートコードは、 pearls のプログラミングに由来します。

void qsort3(int l, int u)
{   int i, j;
    DType t;
    if (l >= u)
        return;
    t = x[l];
    i = l;
    j = u+1;
    for (;;) {
        do i++; while (i <= u && x[i] < t);
        do j--; while (x[j] > t);
        if (i > j)
            break;
        swap(i, j);
    }
    swap(l, j);
    qsort3(l, j-1);
    qsort3(j+1, u);
}

双方向パーティショニング部分には、次の 1 行があります。

if (i > j)

私の質問は、この行を次のように変更できますか?

if(i >= j)

これを行っても問題ないと私が考える理由は次のとおりです。 (i==j)<=> (x[i] == t)x[i] と x[j] を交換する必要がないように forそして、ループを抜け出します。

for次のループのコードはswap(l, j). x[j] == t == x[l] なのでswap(l, j)、パーティションとは関係ありません。

ありがとう

4

1 に答える 1

2

はい、その変更を行うことができます：

i == j の場合、swap(i, j) は報われません。また、i == j の後の次の反復では、無条件に i をインクリメントし、j をデクリメントするため、配列を変更せずにループが終了します。

于 2012-10-09T18:12:51.597 に答える