0

現在、ランダムに生成された数値をソートするためのクイックソートアルゴリズムのベアボーン実装があります。並べ替えは、マージ並べ替えよりも効率的です。ただし、特定の数値セット (逆に並べ替える必要がある逆の数値など) については、ピボットを最適化する必要があります。

int* partition (int* first, int* last);
void quickSort(int* first, int* last) {
    if (last - first <= 1) return;

    int* pivot = partition(first, last);
    quickSort(first, pivot);
    quickSort(pivot + 1, last);
}

int* partition (int* first, int* last) {
    int pivot = *(last - 1);
    int* i = first;
    int* j = last - 1;

    for (;;) {
        while (*i < pivot && i < last) i++;
        while (*j >= pivot && j > first) j--;
        if (i >= j) break;
        swap (*i, *j);
    }

    swap (*(last - 1), *i);

    return i;
}

したがって、このコードでは、パーティショニング ステップのピボットとして乱数を使用するか、最初、中間、および最後の要素の中央値をピボットとして使用します。

どうすればいいですか？

私は並べ替えアルゴリズムを初めて使用しますが、それらの理解はまだ完全ではありません。

4

3 に答える 3

2

これらの行を変更するだけです：

    int pivot = *(last - 1);
    …
    swap ((last - 1), i);

次のようなものに：

    int* pos = (first + rand(last - first));
    int pivot = *pos;
    …
    swap (pos, i);

また

    int* pos = mean_of_three((last - 1), (first), ((first + last) / 2));
    int pivot = *pos;
    …
    swap (pos, i);

ここでmean_of_three、3 つのポインターを取り、平均へのポインターを返します。

于 2012-05-23T06:03:32.073 に答える
2

既に述べたように、配列の最初または最後の要素をピボットとして選択することはベスト プラクティスではなく、アルゴリズムが O(n^2) に陥る原因となります。ピボット選択アルゴリズムの最適な選択は、プログラムが遭遇する可能性のあるデータによって異なります。データが並べ替えられるか、ほぼ並べ替えられる可能性がある場合、O(n^2) の動作を回避するには、ランダム ピボットが非常に適しています (実装も非常に簡単です)。一方、最初の要素ではなく中間の要素を選択するコストは最小限であり、ソートされたデータに対して非常に効果的な保護を提供します。

繰り返しますが、データがソートされない、またはほとんどソートされないことが確実な場合は、3 分割の中央値戦略が最適と思われます。

int PickPivotUsingMedian(int a[], int first, int last)
{
int mid = (first+ right)/2;
if (a[mid ] < a[first]) 
    swap(&a[first],&a[mid ]);
if (a[last] < a[first])
    swap(&a[first],&a[last]);
if (a[last]< a[mid ])
    swap(&a[mid ],&a[last]);

swap(&a[mid], &a[last - 1]);//since the largest is already in the right.
return a[last - 1];
}
于 2012-05-23T06:03:47.550 に答える
1

配列の範囲内でランダムなインデックスを選択し、その要素をピボットとして使用します。

于 2012-05-23T05:58:59.177 に答える