私には何か質問があります。 SedgewickとWayneの本を読んでいるうちに、私は理解できない文章を見つけました。彼らは書いています: - "最初の例では、配列全体を処理する前に2つの再帰呼び出しを行います(2番目の例では、配列全体を処理した後に2つの再帰呼び出しを行います[彼らはMergeSortについて話しています) QuickSortについて話す] 誰かが私にこれら2つの文章の完全なアイデアを説明するかもしれない。 よろしくお願いします!クイックソート、アルゴリズム、第4版 - [Sedgewick、Wayne]
0
A
答えて
1
文章が不必要に混乱しています。実際には、両方のアルゴリズムはまったく同じように働いています。すなわち、A.サブ問題の作成、B.サブ問題の作業、自己再帰的な呼び出し、C.サブ問題に対する解決策の完全な問題への完全な解決へのC.
mergesortでは、入力リストを2つに分割してサブ問題を作成します。
クイックソートでは、選択されたピボットより小さくない値を含む2つの部分に入力配列を分割することによって見つけられます。
mergesortの組換えステップがマージされています。
ソートが同じアレイ上で、場所にが行われるため、クイックソートのための組換えステップは、すなわち何もしない、何もしません。
マージソートの場合、最後のステップはより重要であり、クイックソートは最初のステップです。
3
これは、MergeとQuickSortの両方が使用する分割征服戦略での作業の順番です。
具体的には、MergeSortは作業を小さなチャンクに分割し、再帰呼び出しを行い、2つの結果をマージします。これは、のマージステップを実行する前に、再帰的にと呼ばれます。
QuickSortはまずピボットを見つけ、要素を交換してパーティションを実行し、次に小さなチャンクに分割して再帰呼び出しを行います。がパーティションステップを実行したあと、再帰的にと呼ばれます。
関連する問題
- 1. Red Black Tree削除アルゴリズム(CLR第3版)
- 2. Javaプログラミング言語第4版エクササイズ3.3
- 3. は、Arrays.asListの制限は()この本でのJava第4版
- 4. Perl "逆コンパートメント演算子"(Programming Perl、第4版の例)
- 5. Visual Studio C#2010第4版からの演習
- 6. SCORM 2004第3版オーサリングツール
- 7. SessionHelperをHartlの第3版チュートリアル
- 8. C++入門演習2.27 [第5版]
- 9. join()メソッドとThe Complete Java Reference第9版
- 10. OpenGLプログラミングガイド第7版ソースコードの例
- 11. コードの第2版を完成
- 12. コーディング・インタビューをクラッキングする、第6版、2.8
- 13. "Rails Way"第3版procエクササイズエラーページ360
- 14. Java Connect 4 MinMaxアルゴリズム
- 15. VBAコード - 第4ループでスタック
- 16. クイックソートを乱数化アルゴリズムとランダムに比較する方法
- 17. PGError:ERROR:relation "users"が存在しない - Railsチュートリアル第2版第9章Heroku
- 18. Rails 3ネストしたパーシャル、コレクション、ローカル(レールチュートリアル第2版:第10章、エクササイズ5)
- 19. 第2のベータ版の第三者からコンポーネントを追加する
- 20. 第4章コンマコード - ブックから延長
- 21. Railsチュートリアル第7章、演習4
- 22. Liitle Schemer第4ページ:103値関数
- 23. Nagios NSCA第4変数は常に$ OUTPUT $
- 24. なぜ属性データ第4フィールド1
- 25. 注文を無視第4キャラクタ
- 26. .Net Framework 4完全版とNet Framework 4クライアントプロファイルのターゲット設定
- 27. 配置(TC++ PL第3版の10.4.11を参照)
- 28. Android Devの新機能 - 問題のインストール第2版App/APK
- 29. 第3版デバイスのBluetooth obex受信に失敗しました
- 30. 再定義属性は、Web開発者の第三版のエラー