バブルソート – 日本語百科事典辞書

Bubble_sort

「バブルソート」
バブルソートは、シンクソートと呼ばれることもあり、リストを繰り返しステップ実行し、隣接する要素を比較し、順序が間違っている場合はそれらを交換する単純なソートアルゴリズムです。リストのパススルーは、リストがソートされるまで繰り返されます。比較ソートであるアルゴリズムは、小さい要素または大きい要素がリストの一番上に「バブル」する方法にちなんで名付けられています。
バブルソート
バブルソートの静的な視覚化
クラス
ソートアルゴリズム
データ構造
配列
最悪の場合のパフォーマンス O （（NS
2）。
{O（n ^ {2}）}
比較、 O （（NS
2）。
{O（n ^ {2}）}
スワップ
最高のパフォーマンス O （（）。
{O（n）}
比較、 O （（ 1 ）。 {O（1）}
スワップ
平均パフォーマンス O （（NS
2）。
{O（n ^ {2}）}
比較、 O （（NS
2）。
{O（n ^ {2}）}
スワップ
最悪の場合のスペースの複雑さ O （（）。
{O（n）}
合計、 O （（ 1 ）。 {O（1）}
補助
この単純なアルゴリズムは、実際の使用ではパフォーマンスが低く、主に教育ツールとして使用されます。など、より効率的なアルゴリズムクイックソート、timsort、またはマージはソートなどのPythonやJavaなどの一般的なプログラミング言語に組み込まれたソートライブラリで使用されています。

コンテンツ
1 分析
1.1 パフォーマンス 1.2 ウサギとカメ 1.3 ステップバイステップの例
2 実装
2.1 擬似コードの実装 2.2 バブルソートの最適化
3 使用する
4 バリエーション
5 名前をめぐる議論
6 大衆文化の中で
7 ノート
8 参考文献
9 外部リンク

分析
image"
バブルソートの例。リストの最初から始めて、隣接するすべてのペアを比較し、順序が正しくない場合は位置を入れ替えます（後者のペアは前のペアよりも小さい）。各反復の後
、比較する要素がなくなるまで、1つ少ない要素（最後の要素）を比較する必要が

パフォーマンス
バブルソートの複雑さは、最悪の場合と平均でО（n 2）です。ここで、nはソートされるアイテムの数です。ほとんどの実用的なソートアルゴリズムは、最悪の場合または平均的な複雑さが大幅に向上し、多くの場合O（n log n）になります。挿入ソートなどの他のО（n 2）ソートアルゴリズムでさえ、一般にバブルソートよりも高速に実行され、それほど複雑ではありません。したがって、バブルソートは実用的なソートアルゴリズムではありません。
バブルソートが他のほとんどのアルゴリズム（クイックソートでさえも、挿入ソートではない）に勝る唯一の重要な利点は、リストが効率的にソートされていることを検出する機能がアルゴリズムに組み込まれていることです。リストがすでにソートされている場合（最良の場合）、バブルソートの複雑さはO（n）のみです。対照的に、他のほとんどのアルゴリズムは、平均的なケースの複雑さが優れている場合でも、セットに対してソートプロセス全体を実行するため、より複雑になります。ただし、挿入ソートはこの利点を共有するだけでなく、実質的にソートされた（反転の数が少ない）リストでのパフォーマンスも向上します。さらに、この動作が必要な場合は、アルゴリズムを実行する前にリストを確認することで、他のアルゴリズムに簡単に追加できます。

ウサギとカメ
要素はさまざまな速度でさまざまな方向に移動するため、並べ替え中に要素が移動する必要のある距離と方向によって、バブルソートのパフォーマンスが決まります。リストの最後に移動する必要がある要素は、連続するスワップに参加できるため、すばやく移動できます。たとえば、リスト内の最大の要素がすべてのスワップに勝つため、最初のパスで開始された場合でも、最初のパスでソートされた位置に移動します。一方、リストの先頭に向かって移動する必要がある要素は、パスごとに1ステップより速く移動することはできないため、要素は非常にゆっくりと先頭に向かって移動します。最小の要素がリストの最後にある場合、それを最初に移動するにはn -1パスかかります。これにより、これらのタイプの要素は、イソップの寓話「ウサギとカメ」の登場人物にちなんで、それぞれウサギとカメと呼ばれるようになりました。
バブルソートの速度を向上させるために、カメを排除するためにさまざまな努力が払われてきました。カクテルソートは、最初から最後まで行き、次にそれ自体を逆にして、最後から最初まで行く双方向のバブルソートです。カメをかなりうまく動かすことができますが、O（n 2）の最悪の場合の複雑さを保持します。コムソートは、大きなギャップで区切られた要素を比較し、リストを滑らかにするためにますます小さなギャップに進む前に、カメを非常にすばやく移動させることができます。その平均速度は、クイックソートのようなより高速なアルゴリズムに匹敵します。

ステップバイステップの例
数字の配列「51 4 2 8」を取得し、バブルソートを使用して配列を最小数から最大数に並べ替えます。各ステップで、太字で書かれた要素が比較されています。3つのパスが必要になります。
ファーストパス（ 5
1 4 2 8）（ 1
5 4 2 8）、ここで、アルゴリズムは最初の2つの要素を比較し、5> 1からスワップします。（1 5
4 2 8）（1 4 5 2 8）、5> 4からスワップ（1 4 5 2 8）（1 4 2 5 8）、5> 2からスワップ（1 4 2 5 8）（1 4 2 5 8）、ここで、これらの要素はすでに順序付けられているため（8> 5）、アルゴリズムはそれらを交換しません。
セカンドパス（ 1
4 2 5 8）（ 1
4 2 5 8）（1 4
2 5 8）（1 2 4 5 8）、4> 2からスワップ（1 2 4 5 8）（1 2 4 5 8）（1 2 4 5 8）（1 2 45 8）
これで、配列はすでに並べ替えられていますが、アルゴリズムはそれが完了したかどうかを認識しアルゴリズムは、ソートされていることを知るために、スワップなしで1つの追加のパス全体を必要とします。
サードパス（ 1
2 4 5 8）（ 1
2 4 5 8）（1 2
4 5 8）（1 2 4 5 8）（1 2 4 5 8）（1 2 4 5 8）（1 2 4 5 8）（1 2 4 5 8）

実装

擬似コードの実装
で擬似コードアルゴリズムは、（0から始まる配列）のように表すことができます。
手順バブルソート（A ：リストのソート可能項目）のn ：= 長さ（A ）を繰り返し
スワップ：= falseの
ための I ：= 1 までのn – 1 包括的な DO
/ * 場合、このペアはあるアウトのため * /
もし A > A その後、
/ * スワップそれらと覚えて何かが変わっ * /
スワップ（A 、 A ）
スワップ：= 真の
エンド場合
エンド用までないスワップ終了手順

バブルソートの最適化
バブルソートアルゴリズムは、n番目のパスがn番目に大きい要素を見つけて、それを最終的な場所に配置することを観察することによって最適化できます。したがって、内側のループは、n回目の実行時に最後のn −1個のアイテムを見ることを回避できます。
手順バブルソート（A ：リストのソート項目） N = 長さ（A ）リピート
スワップ：= 偽
のための I = 1 の N – 1つの包括 DO
もし A > A 次に
スワップ（A 、 A ）
スワップ：= trueの
端なら
端のための
N = N – 1 までではないスワップ終了手順
より一般的には、1回のパスで複数の要素が最終的な位置に配置される場合が特に、すべてのパスの後、最後のスワップ以降のすべての要素がソートされ、再度チェックする必要はありません。これにより、多くの要素をスキップできるため、最悪の場合、比較カウントが50％向上し（スワップカウントは向上しません）、新しいコードには「スワップされた」変数が含まれるため、複雑さはほとんどありません。
これを擬似コードで実現するには、次のように記述できます。
手順バブルソート（A ：リストのソート項目） N = 長さ（A ）リピート
newn ：= 0
のため、I = 1 の N – 1つの包括 DO
もし A > A 次に
スワップ（A 、 A ）
newn ：= iが
終了した場合に
終了するため
、N = newn まで N ≤ 1つの端手順
カクテルシェーカーソートなどの代替の変更は、隣接するアイテムを繰り返し比較して交換するという同じ考えを維持しながら、バブルソートのパフォーマンスを改善しようとします。

使用する

バブルソート。リストはデカルト座標系でプロットされ、各点（ x、 y）は値yがインデックスxに格納され
ていることを示しています
。次に、リストはすべてのピクセルの値に従ってバブルソートでソートされます。最大の端が最初にソートされ、小さい要素が正しい位置に移動するのに時間がかかることに注意して
バブルソートは、理解して実装するのに最も簡単なソートアルゴリズムの1つですが、そのO（n 2）の複雑さは、少数を超える要素のリストでは効率が劇的に低下することを意味します。単純なO（n 2）ソートアルゴリズムの中でも、挿入ソートのようなアルゴリズムは通常、かなり効率的です。
その単純さのために、バブルソートは、アルゴリズムの概念、またはソートアルゴリズムを、コンピュータサイエンスの入門学生に紹介するためによく使用されます。しかし、オーウェン・アストラチャンなどの一部の研究者は、バブルソートとそのコンピュータサイエンス教育での継続的な人気を軽蔑するために多大な努力を払い、もはや教えられないことを推奨しています。
ジャーゴンファイル有名な呼び出しは、ボゴソート「原型の強情ひどいアルゴリズム」も「一般的な悪いアルゴリズム」バブルソートを呼び出します。ドナルド・クヌースで、コンピュータプログラミングの芸術その後、いくつかの彼を議論「バブルソートキャッチー名と、それはいくつかの興味深い理論的な問題につながるという事実を除いて、それをお勧めすることは何もないように思われる」と結論は、。
バブルソートは、最悪の場合、実行時間において挿入ソートと漸近的に同等ですが、2つのアルゴリズムは必要なスワップの数が大きく異なります。Astrachanのような実験結果でも、ランダムリストでも挿入ソートのパフォーマンスが大幅に向上することが示されています。これらの理由から、最近のアルゴリズムの教科書の多くは、挿入ソートを優先してバブルソートアルゴリズムの使用を避けています。
バブルソートは、最新のCPUハードウェアとの相互作用も不十分です。挿入ソートの少なくとも2倍の書き込み、2倍のキャッシュミス、および漸近的に多くのブランチの予測ミスが発生します。 Javaで文字列をソートするAstrachanによる実験では、バブルソートは挿入ソートの約5分の1、選択ソートの70％の速度であることが示されています。
コンピュータグラフィックスでは、バブルソートは、ほぼソートされた配列の非常に小さなエラー（2つの要素のスワップなど）を検出し、線形の複雑さ（2 n）で修正する機能で人気がたとえば、ポリゴン塗りつぶしアルゴリズムで使用されます。境界線は、特定のスキャンライン（x軸に平行なライン）でx座標によって並べ替えられ、yをインクリメントすると、次の場所でのみ順序が変更されます（2つの要素が交換されます）。 2本の線の交点。バブルソートは、挿入ソートのような安定したソートアルゴリズムです。

バリエーション
奇偶転置は、メッセージパッシングシステム用のバブルソートの並列バージョンです。
パスは、左から右ではなく、右から左にすることができます。これは、ソートされていないアイテムが最後に追加されたリストの場合に効率的です。
カクテルシェーカーソートは、左方向と右方向のパスを交互に繰り返します。

名前をめぐる議論
バブルソートは、「シンキングソート」と呼ばれることも
たとえば、DonaldKnuthのTheArt of Computer Programming、Volume 3：Sorting and Searchingで、彼はセクション5.2.1「Sortingby Insertion」で、は「適切なレベルに落ち着く」と述べています。ふるい分けまたは沈下技術と呼ばれることも
この議論は、2つの異なるが等しく有効な観点からこのアルゴリズムを簡単に検討できることによって永続化されます。
より大きな値は、とみなされるかもしれない重く、したがって次第にに見ることがシンクに底リストの
小さい値はとみなされるかもしれない軽いので、徐々にに見ることが最大のバブルのトップリストの。

大衆文化の中で
2007年、元GoogleCEOのEricSchmidtは、当時の大統領候補であるBarack Obamaに、100万個の整数を並べ替える最良の方法についてインタビュー中に尋ねました。オバマ氏は少しの間立ち止まり、「バブルソートは間違った道だと思う」と答えた。

ノート
^ コルテシ、アルド「ソートアルゴリズムの視覚化」。
^ “”（coll）java.util.Arrays.sortの””変更されたmergesort “”をtimsort-Java BugSystem””に置き換えます。bugs.openjdk.java.net 。
^ ピーターズ、ティム（2002-07-20）。「並べ替え」。
^ Astrachan、オーウェン（2003）。「バブルソート：考古学的アルゴリズム分析」（PDF）。ACM SIGCSEBulletin。35（1）：1–5。土井：10.1145 /792548.611918。ISSN 0097から8418まで。
^ 「専門用語、ノード：bogo-sort」。
^ ドナルドクヌース。The Art of Computer Programming、第3巻：並べ替えと検索、第2版。アディソン・ウェズリー、1998年 ISBN 0-201-89685-0。セクション5.2.2の106〜110ページ：交換による並べ替え。「 [バブルソートを分析するための]計算で使用される手法は有益ですが、バブルソートはまったく良くないことがわかっているため、結果は期待外れです。ストレート挿入と比較して、バブルソートにはもっと複雑なプログラムが必要で、約2倍の時間がかかります！」（1973年の初版からの引用。）
^ ブラック、ポールE.「バブルソート」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所。
^ Lai Stirland、Sarah（2007-11-14）。「オバマは彼のグーグルインタビューに合格する」。有線。
^ バラク・オバマ、エリック・シュミットバラク・オバマ| Google（Youtube）の候補者。カリフォルニア州マウンテンビュー94043グーグルプレックス：グーグルでの講演。イベントは23:20に発生します。2019年9月7日にオリジナル（ビデオ）からアーカイブされました。

参考文献
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、およびCliffordStein。アルゴリズム入門、第2版。MITプレスとマグロウヒル、2001年
ISBN 0-262-03293-7。問題2-2、40ページ。
分岐予測とキャッシュが存在する場合のソート
エリスホロヴィッツによるデータ構造の基礎サルタージ・サニーとスーザン・アンダーソン・フリード
ISBN 81-7371-605-6
オーウェン・アストラチャン。バブルソート：考古学的アルゴリズム分析

外部リンク
ウィキブックスのアルゴリズムの実装には、次のトピックに関するページがバブルソート
コモンズには、バブルソートに関連するメディアが
ウィキバーシティには、バブルソートに関する学習リソースがあります
マーティン、デビッドR.（2007）。「アニメーションソートアルゴリズム：バブルソート」。 –グラフィカルなデモンストレーション
「Laforeのバブルソート」。（Javaアプレットアニメーション）
OEIS シーケンスA008302（ソート中にkペアスワップを必要とするの順列の数の表（統計））

Bubble_sort&oldid=1048494102″