2

現在、この種の問題が何であるかを把握しようとしています。ウィキペディアのインプレース Quicksort 疑似コードから直接構築されています。これは信頼できると思います。null で終わる 3 文字の「コード」フィールドで構造体の配列をソートしようとしています。

並べ替えはほとんど機能しますが、常にいくつかの要素が適切ではありません。これはどうにかしてピボットに関係しているとしか思えませんが、数時間をじっと見つめていて、どこにも行きませんでした. ありがとう！

void quicksort(Cdir *directory, int left, int right) {

    if (left < right) {
        int pivotIdx = left;
        pivotIdx = partition(directory, left, right, pivotIdx);
        quicksort(directory, left, pivotIdx - 1);
        quicksort(directory, pivotIdx + 1, right);
    }
}

int partition(Cdir *directory, int left, int right, int pivot) {

    char *pivotVal = directory[pivot].code;
    int curIdx = left;
    swap(&directory[pivot], &directory[right]);

    int i;
    for (i = left; i < right; i++) {
        if (strncmp(directory[i].code, pivotVal, 3) < 0) {
            swap(&directory[i], &directory[curIdx]);
            curIdx++;
        }
    }
    swap(&directory[curIdx], &directory[right]);
    return curIdx;
} 

void swap(Cdir *s1, Cdir *s2) {

    Cdir temp = *s1; 
    *s1 = *s2;
    *s2 = temp;
}
4

4 に答える 4

2

私はついにそれを理解しました。文字列比較の "pivotVal" をピボット値 (directory[right]) への直接参照に置き換えると、並べ替えは正常に機能します。その理由をまだ特定しようとしていますが、修正されました。

void quicksort(Cdir directory[], int left, int right) {

    if (left < right) {
        int pivotIdx = left;
        pivotIdx = partition(directory, left, right, pivotIdx);
        quicksort(directory, left, pivotIdx - 1);
        quicksort(directory, pivotIdx + 1, right);
    }
}

int partition(Cdir directory[], int left, int right, int pivot) {

    int curIdx = left;
    swap(&directory[pivot], &directory[right]);

    int i;
    for (i = left; i < right; i++) {
        if (strncmp(directory[i].code, directory[right].code, 3) < 0) {
            swap(&directory[i], &directory[curIdx]);
            curIdx++;
        }
    }
    swap(&directory[curIdx], &directory[right]);

    return curIdx;
} 

void swap(Cdir *s1, Cdir *s2) {

    Cdir temp = *s1; 
    *s1 = *s2;
    *s2 = temp;
}
于 2013-01-30T15:49:26.127 に答える
2

パーティション (..) の次の行にバグがあります。

for (i = left; i < right - 1; i++)

ウィキペディアのコードは、right-1 がループに含まれていることを前提としており、<= である必要があります。

于 2013-01-30T05:56:10.310 に答える
0

swap（pivot、right）とi <rightの目的は、配列からピボットを削除し、1要素小さい配列で作業することであるため、glagoligが提案したようにforループをi<=rightに変更する必要はないと思います。アルゴリズムは私には完全に正しいように見えます。おそらく問題は関数の呼び出し方法にあります。
配列のサイズではなく、配列の最後のインデックスとして右引数を使用して関数を呼び出す必要があります。つまり、Cdirarr[10]がある場合です。クイックソート（arr、0、9）;を呼び出す必要があります。
また、間違った出力の入力の例を投稿すると、人々があなたをもっと助けてくれるのを助けることができます。
私はこれをコメントとして追加したでしょうが、そうするのに十分な担当者がいません:-)

于 2013-01-30T13:53:26.103 に答える