>> [音楽再生]
DOUG LLOYD：すべての権利なので、 バブルソートアルゴリズムであります
あなたは要素の集合をソートするために使用することができます。
のは、それがどのように動作するかを見てみましょう。
>> だから、基本的な考え方の背後にあります バブルソートはこれです。
我々は一般的に高い移動します 一般的に右に値要素、
一般的に大切な要素を下げます 左に、私たちは期待通り。
私たちは、より低いものがでになりたいです 最初、より高いもの
最後になります。
>> 我々はこれをどのように行うのですか？
まあ擬似コードコードで、 我々はしてみましょう、と言うことができます
ゼロ以外の値にスワップカウンターを設定します。
私たちは第二にそれを行う理由当社は、表示されます。
そして、我々は、以下を繰り返します スワップカウンタが0になるまでのプロセス、
または私達はまったくスワップを行うことなくなるまで。
>> へのスワップカウンターをリセット 0それはまだ0ではない場合。
そして、すべてのを見て 隣接する要素のペア。
これらの2つの要素がある場合 ないために、それらを交換し、
スワップカウンターに1を加えます。
あなたが考えている場合 このあなたがそれを視覚化する前に、
これは、下に移動することに気づきます 左に大切な要素
そして、高く、右に要素を大切に 効果的に私たちが何をしたいのかやって、
これらのグループを移動するです その方法の要素の。
それでは、どのようにこれを視覚化してみましょう 私たちの配列を使用して見えるかもしれません
我々がテストするために使用すること これらのアルゴリズムアウト。
我々は再びここにソートされていない配列を持っています、 すべての要素によって示されます
赤でいます。
そして、私はスワップカウンターを設定 ゼロ以外の値に設定します。
私は任意に選びました 負1--それは0ではありません。
我々は、このプロセスを繰り返したいです スワップカウンターまで0です。
私はスワップを設定する理由はここにあります いくつかの非ゼロ値にカウンタ、
なぜならそうでなければ スワップカウンターは0になります。
私たちも開始しません アルゴリズムのプロセス。
だから、再び、ステップはare-- スワップカウンターをリセット
0にし、すべての隣接を見て ペア、および彼らが故障している場合は、
それらを交換し、1を追加 スワップカウンターへ。
それでは、このプロセスを開始しましょう​​。
だから、まず最初にすることです 私たちは、0にスワップカウンターを設定しました
し、我々は探し始めます 各隣接ペアで。
>> だから我々は最初の5と2を見て開始します。
我々は、彼らが外であることを確認 ご注文と私たちはそれらを交換。
そして、私たちは、スワップカウンターに1を加えます。
だから今、私たちのスワップカウンターが1です、 そして、2と5が切り替えられています。
今、私たちは再びプロセスを繰り返します。
>> 私たちは、次の隣接ペアを見て、 5、彼らはまた、順不同でいます1--、
私たちはそれらを交換し、追加します スワップカウンターに1。
その後、我々は5と3を見てください。
彼らは順不同であるので、交換します 彼らと私たちは、スワップカウンターに1を加えます。
その後、我々は5と6を見てください。
彼らは順番にしているので、私たちは実際にはありません 何もこの時間を交換する必要があります。
その後、我々は6と4を見てください。
彼らは順不同でもしているので、私たちはスワップ 彼らと私たちは、スワップカウンターに1を加えます。
>> 今起こっているものに気づきます。
我々はすべての方法最後に6を移動しました。
選択ソートでだから、あなたがしている場合 私たちが何をしたか、そのビデオを見ました
我々は動いてしまいました 建物の中で最小の要素
から本質的にソートされた配列 最大の最小、左から右へ。
バブルソートの場合は、私たちがしている場合 この特定のアルゴリズムに従って、
私たちは実際に構築することになるだろう 右からソートされた配列
左に、最大最小に。
我々は、6を効果的にバブリングしています 最大値、最後にすべての方法。
>> そして、私たちは今宣言することができます それは、ソートされていること、
将来的にiterations-- 配列を通過again--
私たちはもう6を検討する必要はありません。
私たちは、考慮する必要があります ソートされていない要素
我々は、隣接する対を見ているとき。
だから我々は1を終えました バブルソートを通過します。
だから今、私たちが質問に戻って、 スワップカウンタが0になるまで繰り返します。
まあスワップカウンター 4であるので、我々はつもりです
再度このプロセスを繰り返し続けることができます。
>> 私たちは、スワップカウンターをリセットしようとしています 0にし、各隣接ペアを見てください。
だから我々は、彼らがしている1-- 2で始まり、 順不同で、私たちはそれらを交換
私たちは、スワップカウンターに1を加えます。
2と3、彼らは順番にしています。
私たちは何もする必要はありません。
3と5は順序です。
私たちはそこに何もする必要はありません。
>> 5,4、彼らが出ています オーダーの、と私たち
それらを交換し、追加する必要があります スワップカウンターに1。
そして今、我々は、5移動しました 次の最大の要素、
ソートされていない部分の端に。
だから我々は今、それを呼び出すことができます ソートされた部分の一部。
>> 今、あなたは見ています 画面とおそらく言うことができます、
、私はでき配列と 今ソートされます。
しかし、我々はまだそれを証明することはできません。
我々は、保証はありません それはソートだと。
しかし、これはどこにスワップです カウンタは、遊びに来て起こっています。
>> だから我々は、パスを完了しました。
スワップカウンターは2です。
だから我々は、繰り返しになるだろう このプロセスを再度、
スワップカウンタが0になるまで繰り返します。
0にスワップカウンターをリセットします。
だから我々はそれをリセットします。
>> 今すぐ隣り合う見てください。
それは、順番に1と2です。
2と3は順序です。
図3及び図4は、順です。
したがって、この時点で、我々が完了した気づきます すべての隣接ペアを見て、
しかし、スワップカウンターはまだ0です。
>> 私たちは、切り替えるには持っていない場合 その後、任意の要素は、それら
によって、順序でなけれ​​ばなりません このプロセスのおかげ。
だから一種の効率、 その我々のコンピュータ科学者の愛、
私たちは今宣言することができています 配列全体なければなりません
私たちはしなかったため、ソートされ 任意の要素を交換する必要があります。
これはかなりいいです。
>> だから、最悪の場合は何 バブルソートとシナリオ？
最悪の場合には配列です 完全に逆の順序で、
そのため、私たちは各バブルに持っています 大要素のすべて
アレイ全体の方法。
そして、我々は効果的にも持っています バブル小さな要素のすべてのバック
あまりにもアレイ全体のすべての方法、。
そのようにn個の要素のそれぞれが移動しなければなりません 他のn個の要素のすべてを横断。
だから、最悪のシナリオです。
最良の場合には シナリオは、しかし、これは
選択ソートと若干異なります。
配列がすでにあります 私たちが行くとソート。
我々は、いずれかを行う必要はありません 最初のパス上のスワップ。
だから我々は見ているかもしれません 少ない要素で、右？
我々はこれを繰り返す必要はありません 倍以上の数を処理します。
>> だから、何を意味するのでしょうか？
だから、最悪のシナリオは何ですか バブルソート、何のために
バブルソートのための最良のシナリオ？
あなたはこれを推測しましたか？
最悪のケースでは、反復処理する必要があります すべてのn個の要素をn回を横断。
だから、最悪の場合は、n乗されます。
>> 配列は完全である場合 ソートされたしかし、あなただけ
各を見ています 要素の一回。
スワップカウンターがまだ0である場合、 あなたは、この配列がソートされていると言うことができます。
だから最良の場合には、これは 選択よりも、実際に良いです
それは、nのオメガのsort--。
>> 私はダグロイドです。
これはCS50です。