[Powered by Google Translate] [挿入ソート]
[トミーM​​acWilliam] [ハーバード大学]
[これはCS50.TVです]
のは、挿入ソート、番号のリストを取得し、それらをソートするためのアルゴリズムを見てみましょう。
アルゴリズムは、覚えているが、単純にタスクを達成するためのステップバイステップの手順です。
挿入ソートの基本的な考え方は、二つの部分に私たちのリストを分割することです
ソートされた部分と、ソートされていない部分。
>> アルゴリズムの各ステップで、番号が移動され
ソートされていない部分から部分へソート
最終的になるまでは、リスト全体がソートされます。
23、42、4、16、8、15 - 6ここソートされていない番号のリストです。
これらの数値が昇順ですべてではありませんので、それらはソートされていないしている。
我々はまだ選別開始していないので、私達は私達のソートされていない部分すべての6つの要素を考慮します。
>> かつて我々は選別開始、我々はこれらの左側にそれらのソート番号を置くことにしましょう​​。
だから、私たちのリストの最初の要素は、23から始めてみましょう。
我々は、まだ我々のソート部分内の任意の要素を持っていない
ので、単に23が私たちのソート部分の始点と終点であると考えてみましょう。
今、私たちのソート部分は、1つ数、23を持っています
と私たちの無分別の部分は、これらの5つの数字を持っています。
現在、ソートされた部分に私たちのソートされていない部分、42の次の番号を挿入してみましょう。
>> そうするために、我々は23から42を比較する必要があるでしょう - 私たちのソート部分の唯一の要素をこれまでのところ。
四十二は23より大きいので、単に末尾に42を追加することができます
リストのソートされた部分。すばらしい！
現在、私たちのソート部分は2つの要素を持っており、私たちの無分別の部分には、4つの要素を持っています。
だから、ソートされていない部分の次の要素は、ここ4に移動してみましょう。
だから、ここでこれは、ソートされた部分に配置する必要がありますか？
>> 覚えておいて、私たちは、ソートされた順序で、この番号を配置したい
従って私達のソート部分が正しくソートされたすべての回で残っています。
我々は42の右に4を配置した場合、その後私たちのリストは順不同になります。
それでは、私たちのソート部分に右から左へ移動し続けることができます。
私たちが移動すると、まずは、新しい番号のために場所を空けるために下の位置にそれぞれの番号を移動できます。
さて、4も23未満であるので、我々はどちらかそれをここに配置することはできません。
23右の一箇所を移動してみましょう。
>> 我々はソート部分の最初のスロットに4を配置したいと思いますことを意味します。
リスト内のこのスペースは既に空だったかに注目してください、
我々は彼らに遭遇してきたように、私たちは、ソートされた要素を下に移動してきたので。
かしこまりました。だから、私たちは途中でそこにいる。
ソートされた部分に16を挿入することによって、我々のアルゴリズムを続けましょう。
シックスティーンが42未満であるので、の右に42を移動できます。
シックスティーンも23未満であるので、のは、その要素を移動できます。
>> さて、16が4よりも大きい。我々は4と23の間に16を挿入したいようなので、それが見えます。
右から左にリストのソートされた部分を通って移動しながら、
4は、数よりも小さい場合、我々が見てきた最初の番号です
我々は、挿入しようとしている。
だから、今、私たちは、この空のスロットに16を挿入することができます
その、覚えて、我々は以上のソート部分に移動する要素で作成しました
我々は彼らに遭遇してきたように。
>> かしこまりました。今、私たちは4つの要素と2つのソートされていない要素をソートしている。
それでは、ソートされた部分に8を動かしてみましょう。
エイトは42未満です。
エイトは23未満です。
と8は16未満です。
しかし8は4よりも大きくなっています。
そこで、我々は4と16の間に8を挿入したいと思います。
15 - そして今、我々は単にソートするには、左側の1以上の要素を持っています。
フィフティーンは、42未満である
フィフティーンは23未満です。
そして15は16未満です。
しかし、15は8より大きい。
>> 私たちは私たちの最終的な挿入を作りたい場所だから、ここにある。
そして、我々は完了です。
私たちは、ソートされていない部分には多くの要素を持っていない
と私たちのソート部分が正しい順序である。
番号が小さいものから順に並べられます。
それでは、我々だけで実行された手順を説明し、いくつかの擬似コードを見てみましょう。
>> 1行目に、我々はリストの各要素を反復処理する必要があることがわかります
目以外の、ソートされていない部分の最初の要素は単になってしまうので
ソートされた部分の最初の要素。
2行目と3行目では、我々は、ソートされていない部分の我々の現在の場所を追跡している。
要素は、我々が現時点でソート部分に移動している数を表し
jは、ソートされていない部分に私たちのインデックスを表します。
>> 4行目に、我々は、右から左へソート部分を反復している。
私達は私達の現在の位置の左側にある要素回繰り返し処理を停止したい
我々は挿入しようとしている要素より小さい。
5行目で、私たちは右に1スペースに遭遇した各要素をシフトしている。
我々は最初の要素を見つけたときそのように、我々は明らかに挿入するスペースがあるでしょう
我々が移動している要素より小さい。
6行目では、我々は、ソートされた部分を通って左に移動し続けることが私たちのカウンタを更新しています。
最後に、7行目に、我々はリストのソートされた部分に要素を挿入している。
>> 我々は、それが位置jに挿入しても大丈夫だと知っている
我々はすでにそこに右に1スペースであることが使用されている要素を移動したためである。
覚えておいて、我々は、右から左へソート部分を通って移動している、
しかし、我々は左から右にソートされていない部分を通って移動しています。
かしこまりました。現在、アルゴリズムがかかったことを実行中のどのくらいの時間を見てみましょう。
まず、このアルゴリズムは、最悪の場合に実行するためにどのくらい時間がかかるか質問を頼むよ。
我々はビッグO記法を使って、この実行時間を表していることを思い出してください。
私たちのリストをソートするために、我々は、ソートされていない部分の要素を反復しなければならなかった
潜在的にソートされた部分のすべての要素をそれらの各要素に対して。
直感的には、O（n ^ 2）操作のようなこの音。
>> 私たちの擬似コードを見てみると、我々は、別のループ内にネストループを持っている
その、確かに、O（n ^ 2）操作のように聞こえる。
しかし、リストのソートされた部分は、最後の最後まで全体のリストが含まれていなかった。
それでも、我々は潜在的にソートされた部分の冒頭に新しい要素を挿入することができます
アルゴリズムの反復ごとに、
これは、我々はソートの部分に、現在、各要素を見なければならないだろうことを意味します。
だから、それは、我々は潜在的に、2番目の要素に対して1つの比較を行うことができることを意味
第三の要素の2つの比較、などなど。
だから、トータルのステップ数は、1からリストの長さから1を引いたまでの整数の和である。
我々は合計でこれを表すことができます。
>> 我々はここで和に行くことはありませんが、それはこの総和に等しくなることが判明
N / 2 - 同等のN ^ 2/2で2オーバー、 - N（N-1）。
漸近的な実行時の話をするとき、
このn ^ 2という用語は、このn任期を支配しようとしている。
だから、挿入ソートは、Big O（n ^ 2）である。
我々はすでにソートされたリストに挿入ソートを実行した場合。
その場合、我々は、単に左から右へ並べ替え部分を構築したい。
そこで、我々は唯一のnステップの順序に必要になります。
>> 挿入ソートは、nのベスト·ケースの性能を有することを意味し、
その我々はΩ（n）で表す。
そして、それは、挿入ソートのためのそれだ
我々はリストをソートするために使用できる多くのアルゴリズムの一つ。
私の名前はトミーであり、これはCS50です。
[CS50.TV]
ああ、あなたは一度だけ、それが起動する停止することはできません。
ああ、我々はそれをやった - >>ブーム！