8

tl;dr: 双方向リンク リストに効率的にクイックソートを実装することは可能ですか? それについて考える前の私の理解は、いや、そうではありませんでした。

先日、基本的なソート アルゴリズムのイテレータ要件について検討する機会がありました。基本的な O(N²) のものはかなり簡単です。

  • バブル ソート - 2 つの順方向イテレータが適切に機能し、一方が他方をドラッグします。
  • 挿入ソート - 2 つの双方向反復子で十​​分です。1 つは順不同の要素用、もう 1 つは挿入ポイント用です。
  • 選択ソート - 少しトリッキーですが、前方イテレータがそのトリックを実行できます。

クイックソート

std::sort の introsort_loop (gnu 標準ライブラリ/ hp(1994) / Silicon Graphics(1996) など) では、random_access である必要があります。

__introsort_loop(_RandomAccessIterator __first,
         _RandomAccessIterator __last,
         _Size __depth_limit, _Compare __comp)

私が期待するようになったように。

よく調べてみると、クイックソートにこれを必要とする本当の理由が見つかりません。random_access_iterators を明示的に必要とする唯一のものstd::__medianは、中間要素の計算を必要とする呼び出しです。通常のバニラのクイックソートは中央値を計算しません。

パーティショニングはチェックで構成されています

 if (!(__first < __last))
    return __first;

双方向の有用なチェックではありません。ただし、これを前のパーティショニング トラベル (左から右/右から左) のチェックに置き換えることができるはずです。単純な条件は次のとおりです。

if ( __first == __last ) this_partitioning_is_done = true;

双方向イテレータのみを使用してかなり効率的にクイックソートを実装することは可能ですか? 再帰的な深さは引き続き保護できます。

注意。私はまだ実際の実装を試みていません。

4

3 に答える 3

2

通常、リストの中央からピボット要素を選択する必要があるため、ランダム アクセス イテレータが必要です。代わりに最初または最後の要素をピボットとして選択すると、双方向イテレータで十分ですが、事前に並べ替えられたリストの場合、クイックソートは O(n^2) に縮退します。

于 2011-09-28T16:51:20.013 に答える
1

tl;dr: はい

あなたが言うように、問題は中央の要素であるピボット要素を見つけることです.ランダムアクセスでこれを見つけるにはO（1）かかり、双方向イテレータで見つけるにはO（n）（n / 2操作、正確）。ただし、各ステップで、サブ コンテナーを作成する必要があります。左と右には、それぞれ小さい数値と大きい数値が含まれます。クイックソートの主な作業はここですよね？

さて、(再帰ステップのために) サブコンテナを構築するとき、私のアプローチはh、それぞれのフロント要素を指すイテレータを作成することです。サブコンテナに移動する次の要素を選択するたびに、h2 回ごとに進むだけです。h新しい再帰ステップに降りる準備ができたら、これはピボット要素を指します。

O(n log n + n/2) = O(n log n) であるため、実際には重要ではない最初のピボットを見つけるだけで済みます。

実際にはこれは単なる実行時の最適化ですが、複雑さには影響しません。なぜなら、リストを 1 回 (それぞれのサブ コンテナーに各値を配置するため) 繰り返し処理するか、2 回 (ピボットを見つけてからそれぞれの値をそれぞれのサブ コンテナーに配置するため) 繰り返し処理するためです。サブコンテナ) はすべて同じです: O(2n) = O(n)。
これは単に実行時間の問題です (複雑さではありません)。

于 2011-09-28T17:06:22.000 に答える
1

二重リンク リストにクイック ソート戦略を実装してもまったく問題はありません。（片道リストにも簡単に適応できると思います）。ランダムアクセス要件に依存する従来のクイックソートアルゴリズムの唯一の場所は、ピボット要素を選択するために「トリッキー」なものを使用するセットアップフェーズです。実際には、これらすべての「トリック」は、ほとんど同じように効果的なシーケンシャル メソッドに置き換えることができるヒューリスティックにすぎません。

リンクされたリストのクイックソートを以前に実装しました。特別なことは何もありません。適切な要素の再リンクに細心の注意を払う必要があるだけです。おそらくご存じのとおり、リストの並べ替えアルゴリズムの価値の大部分は、明示的な値の交換ではなく、再リンクによって要素を並べ替えることができるという事実に由来します。高速になるだけでなく、リストの要素に関連付けられている可能性のある外部参照の値の有効性も (多くの場合、より重要なことに) 保持されます。

PS ただし、リンクされたリストの場合、マージソートアルゴリズムにより、はるかに洗練された実装が得られ、パフォーマンスも同様に優れていると言えます (特にクイックソートでパフォーマンスが向上する場合を除きます)。

于 2011-09-28T17:16:09.827 に答える