[音楽再生] DOUG LLOYD：[OK]を、ので、マージ ソートは、さらに別のアルゴリズムです 私たちは、整理するために使用することができます 配列の要素。 我々が表示されますとしてではなく、それが持っています 非常に基本的な違い 選択ソート、バブルから ソート、挿入ソート それはそれは本当にかなり巧妙な作り。 マージの基本的な考え方 ソート小さなアレイをソートすることです 次にそれらの配列を組み合わせます 一緒に、またはthem--マージ したがって、ソート順でname--。 マージソート方法はありません これは、ツールを活用することです 何と呼ばれる再帰、 我々はすぐに話してことになるだろう、 しかし、私たちは本当にまだの話をしていません。 ここではマージソートの基本的な考え方です。 、配列の左半分をソート Nを仮定すると、1よりも大きいです。 そして、私が言うとき、私が何を意味しますか nと仮定すると、1はより大きい 私たちは同意することができると思う、その配列の場合 単一の要素で構成されてのみ、 それは、ソートされています。 私たちは実際には必要ありません それには、何もすることができません。 私達はちょうどソートすることを宣言することができます。 これは、単一の要素です。 だから擬似コードは、再び、あります 、配列の左半分を並べ替えます 右半分の配列のソート、 その後、2つの半分をマージします。 さて、すでにあなたは可能性があります だけの種類のは、それを考えて the--あなたはオフに入れているように聞こえます あなたが実際に何もしていません。 あなたは左を並べ替えると言っています 半分、右半分を並べ替えます、 しかし、あなたは言っていません 私はどのようにそれをやっています。 しかし限り、ことを覚えておいてください 配列は、単一の要素であり、 我々はそれをソート宣言することができます。 そして、私たちはそれらを一緒に組み合わせることができます。 そして、それは実際のです マージソートの背後にある基本的な考え方、 ようにそれを打破することです あなたの配列のサイズは1です。 そして、あなたはそこから再構築します。 ソート間違いなくマージ 複雑なアルゴリズム。 そしてそれはまた少しです 可視化するために複雑。 だからうまくいけば、可視化は、私 あなたが一緒に従うのに役立ちますここにあります。 そして、私は物事を物語るために全力を尽くしますよ このもう少しを進めます ゆっくりと、他のものより ただうまくいけばあなたの頭を取得します マージソートの背後にあるアイデアの周り。 だから我々は、同じ配列を持っています 他のソートアルゴリズムの動画 あなたが見てきた場合them-- 6要素の配列。 そして、ここで私たちの擬似コードコードは一種であります 左半分、右半分を並べ替えます、 2つの半分をマージします。 それでは、この非常に濃い赤レンガ色を見てみましょう それの左半分を配列し、ソートします。 だから当分の間、我々が行っています 右のものを無視します。 それはありますが、私たちはしています まだその段階で。 私たちは、ソートじゃありません 配列の右半分。 私たちは、ソート、左にいます 配列の半分。 そして、ちょうどために もう少しであることの 明確なので、私は参照することができます どのステップに私たちがしています、 私は切り替えるつもりです オレンジ色のセットの色。 今、我々はまだ話をしています 元の配列の同じ左半分。 しかし、私はすることができるということでことを望んでいます 様々な項目の色を参照してください、 それはもう少し作りますよ ここで何が起こっているかオフにします。 [OK]を、今私たちが持っています 3要素の配列。 我々は、このの左半分を並べ替えるにはどうすればよいです まだこの段階である配列、？ 我々は左のソートしようとしています 赤れんが色array--の半分 左半分 私は今、オレンジ色に着色してきました。 さて、私たちは試みることができると 再びこのプロセスを繰り返します。 だから我々はまだです 並べ替えしようとしているの真ん中 完全な配列の左半分。 の左半分 配列、私は行きますよ 任意に決定すること左半分 右半分より小さくなり、 これはに起こるので、 3つの要素で構成されています。 そして、私はと言うつもりです 左半分、アレイの左半分 単に要素5です。 五、単一素子であります アレイは、我々はそれをソートする方法を知っています。 だから5がソートされます。 私達はちょうどそれを宣言するつもりです。 これは、単一の要素の配列です。 だから我々は今ソートしました 左の左半分half-- か、私たちはソートしてきました オレンジ色の左半分。 だから今、まだ完了するために、 アレイ全体の左半分、 我々は右半分をソートする必要があります オレンジ、またはこのようなものの。 我々はそれをどのように行うのですか？ さて、私たちは、二つの要素の配列を持っています。 だから我々は左半分を並べ替えることができます 2である配列、の。 二つは、単一の要素です。 だから、それがデフォルトでソートしています。 その後、我々は右半分を並べ替えることができます アレイ、一方の部分の。 これは、デフォルトでは、ソートのです。 これは、今初めてです 我々は、マージ段階に達しました。 我々はあるが、完了しました 我々は今種類のdown--ネストされています それはトリッキーなの一種です 再帰のあるものであり、 あなたを維持する必要があります 私たちがどこにあるかについて頭。 だから我々は、左の並べ替えをしました オレンジ色の部分の半分。 そして今、我々は、ソートの真ん中にいます オレンジ色の部分の右半分。 そして、その過程で、我々は、 ステップであることが今について、 2つの半分をマージします。 私たちは二つの部分を見てみると アレイでは、我々は2と1を参照してください。 どの要素が小さくなっていますか？ 1。 その後、どの要素は小さいのですか？ まあ、それは2または何も。 だから、2です。 だから今、もう一度フレームに 我々は文脈のどこにいますか、 私たちはソートしています オレンジ色の左半分 原点の右半分。 私は、色を変更しました知っています 再び、それは我々があった場所です。 そして、その理由は、私はこれをしませんでした このプロセスであるためであります ダウン反復、続けるつもり。 私たちは左をソートしました 旧オレンジの半分 旧オレンジの右半分。 今、私たちはそれらをマージする必要があります あまりにも一緒に二つの部分。 それは我々がにしている段階です。 だから我々はすべてを考慮する 今グリーンである要素、 元の配列の左半分。 そして、我々はそれらをマージ 同じプロセスを使用して 我々は2をマージするためにしました そして、ちょっと前に1。 左半分、最小 左半分の要素は5です。 上の最小の要素 右半分は1です。 それらのどれが小さくなっていますか？ 1。 上の最小の要素 左半分は5です。 上の最小の要素 右半分は2です。 最小は何ですか？ 2。 そして最後に5と 何も、私たちは5を言うことができます。 [OK]を、そう大きな絵、してみましょう 秒の休憩を取ります 私たちがどこにあると把握。 私たちは、から開始した場合 当初、我々 今のところ完了しました ただ、全体的な配列 ここで擬似コードコードの1ステップ。 私たちは、ソートします 配列の左半分。 元のことを思い出してください 順序が5、2、一つでした。 この工程を経ることにより、 ダウンネストと繰り返し、 問題を破るために継続 ダウンより小さな部分に、 我々は今完了しました 擬似コードのステップ1 全体の出発配列のため。 私たちはその左半分をソートしています。 だから今のがフリーズしましょう​​。 そして今のは、右の並べ替えましょう 元の配列の半分。 そして、我々はによってそれをやろうとしています 同じ反復を通過 物事を分解する工程 して、それらを一緒にマージします。 そうの左半分 赤、または左半分 オリジナルの右半分の アレイは、私は3であると言うつもりです。 繰り返しますが、私はここでは一致しているんです。 あなたは奇妙なを持っている場合 要素の数は、それを 本当にかどうかは関係ありません あなたが左に1を小さくします または右のいずれか小さい方。 たびことに何の問題です 行う上でこの問題が発生しました マージは、あなたが一貫している必要があります。 あなたはどちらか、常にする必要があり 左側を小さくします か、常に確認する必要があり 右側に小さいです。 ここで、私はいつもに選ばれました 左側を小さくします ときに私の配列、または私の サブアレイは、奇数サイズです。 三は、単一の要素であり、 ので、それがソートされます。 私たちは、その前提を活用してきました これまでの私達の全体のプロセスを通して。 だから今のは、右の並べ替えましょう 右半分の半分、 または赤の右半分。 繰り返しますが、我々はこれを下に分割する必要があります。 これは、単一の要素の配列ではありません。 我々は、それがソート宣言することはできません。 だから最初に、我々はつもりです 左半分をソートします。 左半分は、単一の要素であり、 そのため、デフォルトでは、ソートのです。 その後、我々は権利をソートするつもりです 単一の要素である半分、。 これはデフォルトでソートしています。そしていま、 私たちは一緒にそれらの2をマージすることができます。 四つが小さくなり、かつ その後6は小さくなる。 繰り返しますが、私たちは、この時点で何をしましたか？ 私たちは左をソートしました 右半分の半分。 または元に戻ります あった色、 私たちは左をソートしました 柔らかめの赤の半分。 もともとは暗いレンガました 赤と今ではより柔軟な赤です またはそれはよりソフトな赤でした。 そして、我々が並べ替えられてきました 柔らかめの赤の右半分。 さて、よく、彼らはただ、再び緑です 我々は、プロセスを通過しているため。 そして、我々は繰り返す必要が この何度も。 だから今、私たちはそれらをマージすることができます 2つの半分。 そして、それは我々がここで何をすべきかです。 黒い線だから 左半分を分割 そしてこの種の部分の右半分。 私たちは、最小値を比較 array--の左側に または、恐れ入り最小 左半分の値 右の最小値に 半分は3が小さいことがわかります。 そして今、最適化のビット、右？ 何も実際にありません 左側に左。 残りは何もありません 左側に、 私たちは効率的にすることができます ちょうど我々が宣言することができmove-- それの残りの部分は、実際にあります ソートされ、それをタック 何もないので、上 他と比較します。 そして、我々は右側ことを知っています 右側のソートされます。 [OK]を、ので、今のは再び凍結させると、 私達は物語のどこにいるかを見つけ出します。 アレイ全体で、 私たちは何を達成しましたか？ 私たちは、実際に達成しました 今1とステップ2を繰り返します。 我々は左半分をソートし、 我々は右半分を選別しました。 だから今、残っているすべては私たちのためにあります 一緒に、これらの二つの部分をマージします。 だから我々は、最も低い数値の比較します 配列の各半分の要素 順番に進みます。 一つは3未満であるため、1が入ります。 二つは、3未満であるので、2つは行きます。 スリーは5未満であるため、3は行きます。 フォー5未満であるため、4は行きます。 その後、5人が6未満です、 そして、6はすべてのことが残っています。 今、私は知っている、それは手順がたくさんあり​​ました。 そして、私たちは多くのことを残してきました 私たちのきっかけにメモリの。 そして、それは、これらの灰色の四角があるものです。 それがかかったように、それはおそらく感じ 挿入ソートよりも長く多く、バブル ソート、または選択ソート。 しかし、実際には、理由 これらのプロセスの多く 同じtime--で起こっています これは、再び、我々はよものです 我々はについて話すときの話を 将来的には再帰video-- 実際にこのアルゴリズム 明らかに基本的です 何よりも異なります 我々は前に見てきました 有意もあります より効率的に。 何故ですか？ まあ、最悪で ケースシナリオ、我々が持っています n個の要素を分割します し、それらを再結合します。 しかし、我々は再結合するとき 彼らは、私たちがやっています 基本的に倍増して 小さい配列のサイズ。 私たちは、一つの要素の束を持っています アレイ、我々効果的に 2素子アレイに結合します。 そして、我々はそれらを取ります 2素子アレイ とに一緒にそれらを結合 ように4素子アレイ、および、 ように、というように、私たちまで 単一のn個の要素の配列を有しています。 しかし、どのように多くの倍加 それは、nに到達するために時間がかかりますか？ バック電話帳例に考えてみてください。 何回私たちが破れなければならないのです もっと何半分に電話帳、 回我々は電話帳を引き裂くする必要があります 半分に、電話帳のサイズの場合 倍増？ 右、一つだけありますか？ だから、いくつかの並べ替えがあります ここで対数要素。 しかし、我々はまた、まだ、少なくともする必要があります n個の要素のすべてを見てください。 最悪の場合のシナリオではそれほど マージソート、n個のログNで実行されます。 私たちは見ています n個の要素の全て、 私たちはそれらを結合する必要があります 一緒にログのnステップのセットです。 最良の場合のシナリオでは、 アレイが完全にソートされます。 それは素晴らしいことです。 しかし、我々はここにあるアルゴリズムに基づいて、 我々はまだ分割し、再結合する必要があります。 この場合が、 再結合は無効の一種です。 それは必要ありません。 しかし、我々はまだ通過します とにかく全体のプロセス。 最良のケースでそう そして最悪の場合には、 このアルゴリズムは、nログnは時間で実行されます。 マージソートは、間違いなく少しトリッキーです 他の主要なソートアルゴリズムより 我々はCS50について話が、ありました 、実質的に、より強力な。 だからあなたが発見した場合 それを必要とする機会 またはソートするためにそれを使用するには 大規模なデータセット、取得 再帰の考え方の周りにあなたの頭 本当に強力になるだろう。 そして、それはあなたを作るために起こっています プログラムは本当にはるかに効率的 何か他のものに対してマージソート使用します。 私はダグロイドです。 これはCS50です。