[音楽再生] 

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です。