3

似たような投稿がいくつかあることは知っていますが、満足のいく回答はありません。そのため、この質問をもう一度尋ねたいと思います。

以下のコードを検討してください。CRLS Introduction to Algorithms によるクイックソートの実装です

int partition(int* a, int s, int e)
{
    int pivot = a[e];
    int q = s-1;
    for (int i = s; i <= e; i++)
    {
        if (a[i] <= pivot) {
            q++;
            int tmp = a[q];
            a[q] = a[i];
            a[i] = tmp;
        }
    }
    return q;
}

void quickSort(int* a, int s, int e)
{
    if (e > s) {
        int q = partition(a, s, e);
        quickSort(a, s, q-1);
        quickSort(a, q+1, e);
    }
}

安定した並べ替えアルゴリズムは、等しいキー (値) を持つレコードの相対的な順序を維持します。クイックソートがそれらの1つではない理由がわかりません。隣接していない要素間にはスワップがありますが、なぜそれが不安定になるのかはまだわかりません。誰かがこれを説明する例を挙げてくれることを本当に願っています。

ありがとうございました。

4

2 に答える 2

2

安定した並べ替えアルゴリズムでは、スワッピングまたはスプリングは隣接する要素でのみ発生します。たとえば、マージソートでは、要素は1つの単位になり、それに応じてマージ関数を使用してソートされます.線形ソートを考慮すると、自明だと思います。しかし、クイックソートではそうではありません。

于 2015-06-21T13:59:14.693 に答える