私には何か質問があります。 SedgewickとWayneの本を読んでいるうちに、私は理解できない文章を見つけました。彼らは書いています： - "最初の例では、配列全体を処理する前に2つの再帰呼び出しを行います（2番目の例では、配列全体を処理した後に2つの再帰呼び出しを行います[彼らはMergeSortについて話しています） QuickSortについて話す] 誰かが私にこれら2つの文章の完全なアイデアを説明するかもしれない。 よろしくお願いします！クイックソート、アルゴリズム、第4版 - [Sedgewick、Wayne]
文章が不必要に混乱しています。実際には、両方のアルゴリズムはまったく同じように働いています。すなわち、A.サブ問題の作成、B.サブ問題の作業、自己再帰的な呼び出し、C.サブ問題に対する解決策の完全な問題への完全な解決へのC.
mergesortでは、入力リストを2つに分割してサブ問題を作成します。
クイックソートでは、選択されたピボットより小さくない値を含む2つの部分に入力配列を分割することによって見つけられます。
mergesortの組換えステップがマージされています。
ソートが同じアレイ上で、場所にが行われるため、クイックソートのための組換えステップは、すなわち何もしない、何もしません。
マージソートの場合、最後のステップはより重要であり、クイックソートは最初のステップです。
これは、MergeとQuickSortの両方が使用する分割征服戦略での作業の順番です。
具体的には、MergeSortは作業を小さなチャンクに分割し、再帰呼び出しを行い、2つの結果をマージします。これは、のマージステップを実行する前に、再帰的にと呼ばれます。
QuickSortはまずピボットを見つけ、要素を交換してパーティションを実行し、次に小さなチャンクに分割して再帰呼び出しを行います。がパーティションステップを実行したあと、再帰的にと呼ばれます。