[音楽再生] 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です。