[Powered by Google Translate] [マージソート]
[ロブボーデン - ハーバード大学]
[これはCS50です。 - CS50.TV]
マージソートについてお話しましょう​​。
ここまでは、バブルソート、挿入ソート、選択ソートを見てきました。
私は良いが何を意味するのかで私の手を波のようなものだけどね、
マージソートは、一般的に、これらの3種類のどれよりも高いパフォーマンスを発揮します。
>> しかし、マージソートの話の前に、のは2ソートされたリストをマージすることについてお話ししましょう​​。
我々は、これらのように、2つのソートされたリストを取る処理を呼ぶことにします、
そしてそれらのシングルソートされたリストを作ることを - リストをマージする。
どのように我々はこれを行うことができますか？
まあ、ひとつのアイデアは、ちょうど他のリストの最後にあるリストを堅持することです
し、結果のリストをソートします。
>> この作品が、それは不必要な多くの作業。
私達はちょうどソートよりも高速に行うことができます。
1間違った考えはちょうど各リストから交互にコップを取ることであることに注意してください。
それは、最初はその作品のように思えるかもしれませんが、
16と23は場違いであることに注意してください - 私たちは4、8、15、23、16で終わるのをやって。
これは、マージされたリスト内の連続表示される2つの要素
同じ初期リストにあります。
15と16の両方が左のリストに表示されます。
トリックは、両方のリストが既にソートされているという事実を活用することです。
これは、我々はちょうど両方のリストの最初の要素を見ればことを意味します -
ここで、4,8 - そのうちの一つはまた、マージされたリストの最初の要素でなければなりません。
さて、その理由は何ですか？
これらのリストの両方がすでにソートされている、
我々は2つ​​のリストを結合するときなど、4または8のいずれかが最小の要素でなければなりません。
この場合、最小は4であり、
ので、我々は4を取り出して私達のマージされたリストの最初の要素にすることができます。
今、私たちは最初のリストの残りの3つの要素をマージし続ける
2番目のリストの4つの要素。
>> もう一度、我々は唯一の両方のリストの最初の要素に注目する必要があります。
2の小さい方が、私たちのマージされたリストの二番目の要素でなければなりません。
今回は、8と15の間に最小は8ですので、私たちはその挿入
私たちのソートされたリストの2番目の要素として。
我々は両方のリストの最初の要素を比較続けることができます
と2のうち小さい方を削除します。
15と23を比較すると、15が小さくなるので、それは我々の3番目の要素です。
今では16と23を比較すると、16が小さくなっています。
だからそれは第四の要素です。
>> 2要素は行の同じリストから来ていることに注意してください。
これはなぜマージリストが2つのリストから別の要素だけではできません。
50と23を比較すると、23が小さいので、我々はそれを選択します。
50と42の間、42が小さくなっています。
50と108の間に、50が小さくなっています。
そして最後に、我々はちょうど108を持っているので、それは私たちのリストの最後に行く必要があります。
我々は素晴らしい、ソートされたリストを持っていることに注意してください。
我々は2つ​​のリストの最初の2つの要素を比較して毎回
我々は、マージされたリストの次の要素を決定することができた。
これは、もし最終的なリストはここに、nは8であるn個の数字が含まれていることを意味します
その後、我々は適切な場所にそれらの数字のすべてを取得するために最大nの比較であります。
そのようなアルゴリズムは、線形時間で実行するように言われています
しかしここではその心配はありません。
>> マージのために我々のアルゴリズムを使用して、我々は、高速マージソートアルゴリズムを作ることができます。
それでは、私たちのリストをリセットしてみましょう。
マージソートの過程で、2つの大きなステップがあります。
まず、継続的に半分にコップのリストを分ける
我々はそれらのちょうど1カップとリストの束を持っているまで。
リストには、奇数が含まれている場合は心配しないでください
そして、それらの間完全にきれいにカットすることはできません。
ちょうど任意インチ余分なカップを含めるリスト選ぶ
それでは、これらのリストを分割できます。
今、私たちは2つのリストを持っています。
今、私たちは4リストを持っている。
>> そして今、我々は各リストの1杯で8リストを持っている。
だからステップ1のそれだ。
ステップ2では、我々は繰り返し我々の前に学習したマージ·アルゴリズムを使用してリストのペアをマージします。
108と15のマージは、リスト15、108で終わる。
50と4のマージ、我々は4、50で終わる。
8と42のマージ、我々は8、42で終わる。
と23と16をマージ、私たちは16日、23日で終わる。
これで、すべての私達のリストのサイズは2である。
4の各リストがソートされていることに注意してください。
>> だから我々は再びリストのペアをマージを開始することができます。
15と108と4と50のマージ -
最初に108、次に50、15、4を取る。
8、42、16、23、マージ
我々はまずそれから、次に、8、16、23、42取る。
だから今我々はソートされているそれぞれのサイズ4のちょうど2つのリストを持っています。
だから今我々は、これらの2つのリストをマージします。
まず4を取る。
その後、我々は8を取る。
その後、我々は次に次に次に次に15と16、23、42、50、108を取る。
そして、我々は完了です。
我々は今、ソートされたリストを持っています。
だから、これは正確にはどのくらいの速さだったのですか？
専門用語では、マージソートはO（n log n）である
一方、バブルソート、挿入ソート、選択ソートのすべてはO（n²）である。
あなたはすぐに学ぶように、実際には、あなたは、ソートを思い付くことができません
それは一般的なケースではO（n log n）のよりもパフォーマンスが向上します。
あなたはまだそれを見ていない場合は、再度、このビッグO記法の心配はありません。
>> 私たちは本当に大きなリストをソートしたい場合だけ、これが意味することを知っている
バブルソート、挿入ソート、選択ソートは、潜在的に取ることができる
大幅に長くマージソートより。
これは、マージソートは、すべてのリストに対して速くなることを意味するものではありません
あるいは、特定のサイズの下の任意の単一のリストを表示してください。
たとえば、挿入ソートは、5つの要素よりも小さいすべてのリストの最速のソートであるかもしれません。
実際には、マージソートは50要素のような小さなリストのほうが高速です。
>> しかし、この余分な速度は価格なしで来ていません。
代わりにリストを取り、リストを変更し、当社の他の種類のとは異なり、
私たちは、ソートされたリストを取得するまで、マージソートは、いくつかの追加のスペースを必要と
一緒に2つのリストをマージすることができます。
我々はすぐにマージされたリストを格納するためにマージされているリストを使用することはできません
我々はまだマージする必要がある要素を上書きするかもしれないので。
このスペースには、価格のビットですが、それは通常無理ではありません。
そして、それはマージソートのためのそれだ。
>> 私の名前はロブ·ボーデンであり、これはCS50です。
[CS50.TV]
- と選択ソート。
[笑]
ああ、私はそれを提示された方法に切り替えているため、あまりにもを取るようになった。
左側のリスト。それはタイプミスでした。
[misspoke]私がしくじった -
[笑]
私がわからない -