[Powered by Google Translate] [バブルソート] [ジャクソンSTEINKAMPハーバード大学] [これはCS50です。 CS50TV] バブルソートは、ソートアルゴリズムの一例である -  それは、内の要素のセットをソートするための手順です 昇順または降順。 例えば、あなたが数字から成る配列をソートしたい場合 [3、5、2、9]、バブルソートの正しい実装では、戻ってくる ソートされた配列[2、3、5、9]を昇順インチ 今、私は、このアルゴリズムがどのように動作するかを擬似コードで説明するつもりです。 

3、2、9、6、5  - レッツは、我々は5つの整数のリストをソートしていると言う。 アルゴリズムは、最初の二つの要素、3と2を見て、開始 彼らは互いに相対的順序を外れているのであればチェックする。 彼らは -  3は2より大きい。 昇順になっているために、彼らは他の方法で回避する必要があります。 そこで、我々はそれらを交換。 [2、3、9、6、5]：今のリストは、このように見えます。 

次に、我々は2番目と3番目の要素は、3と9を見てください。 彼らは互いに相対的に正しい順番にしている。 アルゴリズムでは、それらを交換していません9未満でそうなっていることを、3である。 次に、我々は9と6を見てください。彼らは順不同だ。 

だから、私たちは9が6よりも大きいので、それらを交換する必要があります。 最後に、我々は最後の2つの整数、9と5を見てください。 彼らは、順不同でいるので、彼らはスワップする必要があります。 リストを通して最初の完全なパスの後、 それはこのようになります：[2、3、6、5、9]。 悪くない。これは、ほぼソートされている。 しかし、我々はそれが完全にソートされた取得するために再度リストを介して実行する必要があります。 二人は3未満であるので、我々はそれらを交換しないでください。 

三つは、6未満であるので、我々はそれらを交換しないでください。 シックスは5より大きい。我々は、交換しました。 シックスは9未満である。我々はスワップしません。 の2回目のパスの後、それは次のようになります[2、3、5、6、9]。パーフェクト。 さて、擬似コードで書いてみましょう。 基本的には、リスト内の各要素に対して、我々はそれを見る必要がある そして直接その右にある要素。 彼らは互いに相対的順序が一致していない場合 - つまり、左側の要素なら 右側の1を超えている - 私たちは2つの要素を交換してください。 

我々は、リストのすべての要素のためにこれを行うには、我々は一つの通過を作りました。 今、私たちは、単にリストを確実にするためにパススルー十分な回数を行う必要が 完全に、正しくソートされます。 しかし、我々はリストに通過する方法を何回も持っている 我々がやっていることを保証するものでは？ 我々は完全に後方にリストを持っている場合だけでなく、最悪のシナリオです。 それは数に等しいパススルーの数を取り 要素がn-1の。 これは直感的に意味をなさない場合は、単純な例だと思う - リスト[2,1]。 

これは正しくソートするために1パススルーかかるとしている。 [3、2、1]  - 最悪の場合、3つの要素で逆方向にソートすることです それは、ソートに2回の反復を取るつもりです。 1反復後に、それが[2、1、3]です。 第二利回りソートされた配列[1、2、3]。 だからあなたが一般的には、配列を経由する必要はありません知っている、 nは配列内の要素の数はn-1回、より。 最大の要素は "バブルアップ"する傾向があるので、それはバブルソートと呼ばれています かなりのスピードで右へ。 実際には、このアルゴリズムは非常に興味深い挙動を持っています。 

配列全体を通してメートルの繰り返しの後、 右端のm要素が保証されています 自分たちが正しい場所に並べ替えることができます。 あなたは、あなた自身のためにこれを確認したい場合 我々は完全に後方にリスト[9、6、5、3、2]でそれを試すことができます。 リスト全体を1回通過した後、 [書き込みの音] [6、9、5、3、2]、[6、5、9、3、2]、[6、5、3、9、2]、[6、5、3、2、9] 右端の要素9は、その適切な場所にあります。 パススルー秒後、6 'バブリングアップ "しなければならないでしょう 右端から2番目の場所。 6と9  -   - 右側にある2つの要素は、自分たちが正しい場所になります 最初の二つのパススルー後。 

ですから、どのように我々は、アルゴリズムを最適化するために、これを使用することができますか？ さて、配列を介して1つの反復の後 私たちは実際に右端の要素をチェックする必要はありません 私たちが知っているので、それはソートだ。 2回繰り返した後、我々は、右端の2つの要素が整っている確かに知っている。 だから、一般的には、k回反復した後の完全な配列を介して、 私たちが知っているので、最後のk個の要素をチェックすることは冗長である 彼らはすでに正しい場所にいる。 

ですから、n個の要素の配列をソートしている場合、 最初の反復で - 最初のn-0  -  you'llは、すべての要素をソートする必要があります。 2回目の反復では、すべての要素が、最後を見てみなければならないでしょう -  最初のn-1。 もう1つの最適化リストが既にソートされているかどうかを確認することであるかもしれません 各反復後。 それが既にソートされている場合、我々はそれ以上の反復を行う必要はありません リストをスクロール。 どのように我々はこれを行うことができますか？ まあ、我々はリストのパススルー上の任意のスワップを行わない場合、 それは我々が何を交換しなかったため、リストが既にソートされていることは明らかです。 だから我々は間違いなく、再びソートする必要はありません。 

おそらく、あなたがに "ソートされていない 'と呼ばれるフラグ変数を初期化することができ あなたは上の任意の要素をスワップする必要がある場合はfalseとtrueに変更 配列を介して1つの繰り返し。 または同様に、あなたが作るどのように多くのスワップをカウントするカウンタを作る 任意の反復で。 、イテレーションの終わりには、要素のいずれかを交換しなかった場合 あなたは、リストが既にソートされて、作業が終わっている知っている。 バブルソートは、他のソートアルゴリズムのように、することができます 順序付けメソッドを持つすべての要素のために働くために微調整。 

それはあなたの最初の1つが言う方法を持つ2つの要素を考えると、ある に等しいか、または秒未満、より大きい。 例えば、あなたが言ってアルファベットの文字を並べ替えることができ その<B、B <cなど 日曜日は月曜日未満であるか、曜日を並べ替えることができ これは火曜日未満です。 

バブルソートは、非常に効率的なまたは速いソートアルゴリズムを意味するものではまったくない。 その最悪の場合のランタイムがnのビッグOである² あなたは、リストをn回の反復をしなければならないので、 すべてのn個の要素をチェックして各nxnの、パススルー= nの²。 この実行時間は要素数のように、増加を選別していることを意味します ランタイムは二次関数的に増加します。 

しかし、効率がプログラムの主要な関心事ではない場合 またはあなただけの少数の要素をソートしている場合、 あなたはバブルソートが便利な場合もありますので、 それは理解することが最も簡単なソートアルゴリズムの一つだ とコードに。 また、理論の翻訳の経験を得るための素晴らしい方法です 実際の機能コードに変換アルゴリズム。 まあ、それはあなたのためのバブルソートです。見てくれてありがとう。 CS50.TV