9

私は「コーディングインタビューのクラッキング」（5e、119ページ）の本で分配関数を見てきました。以下にコピーしました：

int partition(int arr[], int left, int right){
    int pivot = arr[(left + right) /2 ]; // Pick pivot point
    while (left <= right) {
        // Find element on left that should be on right
        while (arr[left] < pivot) left++;
        // Find the element on right that should be on left
        while (arr[right] > pivot) right--;
        // Swap elements, and move left and right indicies
        if (left <= right) {
            swap(arr, left, right); // swaps elements
            left++;
            right--;
        }
    }
    return left;
}

この配列が与えられた場合：

1 2 3 4 5 6 3

これは、パーティションが段階的に私のために働いた方法です

  1. 4はピボット値です。左=0、右= 6

  2. 左=3、右=6。交換します。

    1 2 3 3 5 6 4

  3. 左=4、右=4。終了

しかし、私が最終的に得た配列は次のとおりです。

1 2 3 3 5 6 4

4前後に分割されていません。手順を間違って実行しましたか、それともアルゴリズムが正しくありませんか？アルゴリズムの再現を再確認し、正しくコピーしました。

また、パーティションが左に戻っている理由はわかりませんが、ピボットを返しているのでしょうか。

ウィキペディアのパーティションとクイックソートの実装は理解していますが、ここで何が起こっているのか頭を悩ませようとしています。

4

2 に答える 2

6

パーティションの目的は、アレイを 2 つのセグメントに分割することです。最初のセグメントには要素 [1,2,3,3] が含まれます。これらの値はすべて 4 以下です。2 番目のセグメントには要素 [5,6,4] が含まれます。これらの値はすべて 4 以上です。

パーティション関数は、2 番目のセグメントの開始位置を返します。この場合、インデックス 4 から始まります。

于 2012-07-23T03:49:12.073 に答える