>> [音楽再生]
>> 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です。