1

私はアルゴリズム クラス プロジェクトを行っています。このプロジェクトでは、QuickSort の実装を修正して改善を提案する必要があります。これらの提案の 1 つを次に示します。配列内のピボットを選択せず​​、パーティション メソッドの最後のスワップを回避します。

彼がこれで何を意味しているのか正確に理解するのに苦労しています. ピボットがなければ、QuickSort のままでよいのでしょうか? これが何を意味するのかについての洞察をいただければ幸いです。これは、変更する Java コードです。

public void quickSort() {
    recQuickSort(0, nElems - 1);
}

public void recQuickSort(int left, int right) {
    if (left >= right)
        return;
    long pivot = a[right];
    int mid = partition(left, right, pivot);
    recQuickSort(left, mid - 1);
    recQuickSort(mid + 1, right);
} // end recQuickSort()

public void swap(int dex1, int dex2) { // swap two elements
    long temp = a[dex1]; // A into temp
    a[dex1] = a[dex2]; // B into A
    a[dex2] = temp; // temp into B
} // end swap()

public int partition(int left, int right, long pivot) {
    // assuming pivot == a[right]
    int leftPtr = left - 1; // left of the first element
    int rightPtr = right; // position of pivot
    while (true) {
        while (a[++leftPtr] < pivot)
            ; // find bigger
        while (leftPtr < rightPtr && a[--rightPtr] >= pivot)
            ; // find smaller
        if (leftPtr >= rightPtr) // if pointers cross,
            break; // partition done
        else
            // not crossed, so
            swap(leftPtr, rightPtr); // swap elements
    } // end while(true)
    swap(leftPtr, right); // restore pivot
    return leftPtr; // return pivot location
} // end partition()
4

2 に答える 2

0

私はあなたのためにそれを実装しようとするつもりはありませんが、この提案された「改善」の私の解釈は、ピボット値を選択し、その値のどちら側にあるかに応じて配列をセクションに分割することを望んでいるということです. 、ただし、その値を含む配列エントリを特別に扱わないでください。

難しいことではありませんが、アルゴリズムのパフォーマンスはまったく改善されません。また、他の意味での改善が大幅に改善されるとは思えません。

于 2012-10-11T22:26:34.083 に答える
0

彼は、配列内の実際の要素をピボットすることを望んでいないようです。メソッドの最後のスワップのポイントは、ピボットを配列内の正しい場所に移動することです (呼び出しpartition()後にピボット要素を移動することは決してないことに注意してください)。partition()

編集「ピボットを使用しない」と混乱している場合でも、ピボットを使用しています...それは配列内のピボットではありません。手でクイックソートを行うことを想像してみてください。ピボットする任意の値を選択できます。

問題は、そのスワップが実際にはパフォーマンスにまったく悪影響を及ぼさないことです。一方、これは迅速な変更のはずです...

于 2012-10-11T22:30:21.347 に答える