2

最初のものは単純で、反転が見つかるまで両側から歩くだけです。

/*C++ version, [first, last), last needs --first to fetch the last element*/
/*returns the middle of partitioning result*/
int* partition( int *first, int *last, int pivot ) {
    while (true) {
        while (*first < pivot) ++first;
        --last;//Don't edit this, it's true.
        while (pivot < *last) --last;
        if (!(first < last)) return first;
        swap(*first, *last);
        ++first;
    }
}

2 つ目 (「アルゴリズムの紹介 」に示されています) は次のとおりです。

int* partition( int a[], int n, int pivot ) {
    bound = 0;
    for ( i = 1; i != n; ++i )
        if ( a[i] < pivot )
            swap( &a[i], &a[++bound]);
    swap(a, a + bound);
    return a + bound;
}

2 つ目の不変条件は、「バインド前のすべての要素がピボットより小さい」です。

Q: 2 つのバージョンの長所と短所は何ですか?

最初に 1 つを与え、2 つ目はイテレーター (ポインター) で ++ 操作を必要とするためForwardIterator、リンクされたリストのイテレーターのようなものに適用できます。その他のヒントは？

4

1 に答える 1

3

2 つのアルゴリズムの基本的な考え方に関する限り、どちらも正しいです。それらは同じ数の比較を行いますが、2 番目のものは最初のものよりも多くのスワップを行います。

1 9 2 8 3 7 4 6 5これは、アルゴリズムが5 をピボットとして使用して配列を分割するときに、アルゴリズムをステップ実行することで確認できます。最初のアルゴリズムが 2 つの数値を交換すると、そのいずれにも二度と触れません。2 番目のアルゴリズムは、最初に 9 と 2 を交換し、次に 9 と 3 を交換するというように、複数の交換を行って 9 を最終的な位置に移動します。

他にも違いがあります。私が間違いを犯していなければ、これは最初のアルゴリズムが配列をどのように分割するかです:

1 9 2 8 3 7 4 6 5
f                 l
1 9 2 8 3 7 4 6 5  # swap 9,5
  f             l
1 5 2 8 3 7 4 6 9  # swap 8,4
      f     l
1 5 2 4 3 7 8 6 9  # return f = 5
        l f

これは、2 番目のアルゴリズムが配列を分割する方法です。

1 9 2 8 3 7 4 6 5  # 1<5, swap 1,1
bi      
1 9 2 8 3 7 4 6 5  # 9>5, no swap
  bi
1 9 2 8 3 7 4 6 5  # 2<5, swap 9,2
  b i
1 2 9 8 3 7 4 6 5  # 8>5, no swap
    b i
1 2 9 8 3 7 4 6 5  # 3<5, swap 9,3
    b   i
1 2 3 8 9 7 4 6 5  # 7>5, no swap
      b   i
1 2 3 8 9 7 4 6 5  # 4<5, swap 8,4
      b     i
1 2 3 4 9 7 8 6 5  # 6>5, no swap
        b     i
1 2 3 4 9 7 8 6 5  # 5=5, exit loop, swap 9,5
        b       i
1 2 3 4 5 7 8 6 9  # return b = 4
        b       i

他のアルゴリズムは 2 回しかないのに対し、5 回のスワップを行うことに注目してください。また、配列の最後の項目を中央の配列に移動します。この場合、最後のアイテムがたまたまピボットなので、中央に移動したのはピボットですが、これは一般的なケースではありません。

于 2013-09-19T08:47:52.573 に答える