>> [音楽再生]
>> DOUG LLOYD：だから挿入ソートは別です このアルゴリズムは、我々は配列をソートするために使用することができます。
このアルゴリズムの背後にある考え方 あなたのソートされた配列を構築することです
代わりに、外要素をシフトします あなたが行くような方法は、部屋を作るために。
これは多少異なります 選択ソートやバブルから
ソート、例えば、どこ 私たちは場所を調整しています、
ここで、我々はスワップを作っています。
>> この場合、私たちは実際にしています やってスライド要素であります
道のうち、オーバー。
このアルゴリズムをどのように 擬似コードで働きますか？
まあちょうど任意としましょう 配列の最初の要素は、ソートされます。
我々は場所に構築しています。
>> 我々はつもり一度に一つの要素に行くしていて、 それを構築し、私たちが見る最初の事
1つの要素の配列です。
定義することにより、1 要素の配列がソートされます。
>> その後、我々は、このプロセスを繰り返しますuntil-- 我々は、以下の処理を繰り返します
すべての要素まで、ソートされています。
次のソートされていない要素を見て、 ソートされた部分に挿入し、
必要な数をシフトさせることにより 道の外の要素の。
うまくいけば、この可視化 あなたがです正確に何を参照するのに役立ちます
挿入ソートで起こっ。
>> だからもう一度、ここで私たちです 全体未ソート配列、
すべての要素が赤で示されています。
そしてのは従ってみましょう 私たちの擬似コードのステップ。
まず最初にすることは、私たちが呼んでいます 配列の最初の要素、ソート。
だから我々はちょうどつもりだと言います 5、あなたは今ソートされています。
>> その後、我々は次を見て 配列のソートされていない要素
そして我々はそれを挿入したいです ソートされた部分に、
要素の上にシフトすることもできます。
だから、二人は次のソートされていないです 配列の要素。
明らかに、前所属します 5ので、私たちがやるつもりです
ソートの第二のために取って2を保持しています、 以上の5をシフトし、次に2を挿入
5の前に、どこに行く必要があります。
そして今、我々は、2つのソートされていると言うことができます。
>> あなたが見ることができるように、我々はこれまでのところ唯一きました 配列の二つの要素を見ました。
私たちは見ていません まったく休むが、我々はしました
でソートし、これらの2つの要素を持って 変速機構の方法。
>> だから我々は、再度処理を繰り返します。
次のソートされていないを見てください 要素は、それは一つです。
、のは、第二のために、その脇に保持してみましょう 以上のすべてをシフトし、1を入れて
どこに行く必要があります。
>> 繰り返しますが、まだ、私たちは今までしました 1、2、5を見ました。
我々は来ている他に何かわかりません、 しかし、我々はこれらの3つの要素をソートしました。
>> 次のソートされていない要素があります 3、私たちは横に置いておきましょう。
私たちは私たちの上にシフトします これは、この時間に必要
以前のように、すべてではありません 2つのケースは、それだけで5です。
そして、我々は三スティックよ、 2と5の間。
>> シックスは、次のソートされていないです 配列に要素。
実際には6 5よりも大きいので、 私たちも、任意のスワップを行う必要はありません。
私達はちょうど右の6つのタックすることができます ソートされた部分の端。
>> 最後に、4つです 最後にソートされていない要素。
だから私たちは横に置いておきましょう、以上のシフト 我々はオーバーシフトする必要がある要素、
そして、それが属する4を置きます。
そして今、見て私たちはソートしました すべての要素の。
挿入に注意してください ソート、我々は持っていませんでした
アレイ全体を前後に移動します。
私たちは、アレイにわたって行ってきました 一度、私たちは物事をシフト
ために、我々はすでに、遭遇するだろうと 新しい要素のための部屋を作るために。
>> だから、最悪の場合は何 挿入ソートとシナリオ？
最悪の場合、 アレイは、逆の順序です。
あなたは、n個の要素の各々をシフトする必要があります n個の位置まで、ひとつひとつの時間、私たち
挿入を行います。
それはシフトの多くのです。
>> 最良の場合には、 アレイが完全にソートされます。
ソートの何が起こったかのように 例では5と6と、
私達はちょうどそれをタックそうな場所 任意のシフトを実行することなく、
我々は、本質的にそれを行うだろう。
>> あなたは私たちのことを想像した場合 アレイは、6を通じて一つでした
私たちはすることから始めたいです いずれかを宣言すると、ソートされます。
二つは、私たちはただ缶1の後に来ます 1と2がソートされても、[OK]を、言います。
三は[OK]を、ので、2つの後に来ます、 1と2と3がソートされています。
>> 私たちはしている、任意のスワップを行っていません ちょうどこの任意の行を移動します
私たちが行くようにとの間でソートされ、ソートされていません。
効果的に私たちは一例で行ったように、 我々が進むにつれて、青の要素を回します。
だから、最悪の場合の実行時間は、その後、何ですか？
覚えておいてください、私たちはそれぞれをシフトする必要がある場合 n個の要素おそらくn個の位置、
うまくいけば、それはあなたを与えます 最悪の場合は、そのアイデア
ランタイムは、nのビッグOの二乗です。
>> 配列は完全である場合 私たちがしなければならないソート、すべての
一つ一つの要素を見ています 一度、その後、我々は完了です。
そのように最良の場合には、n個のオメガです。
>> 私はダグロイドです。
これはCS50です。