バブルソート

バブルソート

バブルソートの静的可視化[1]
クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O(n^{2})}$ 比較、交換${\displaystyle O(n^{2})}$
最高の パフォーマンス	${\displaystyle O(n)}$ 比較、交換${\displaystyle O(1)}$
平均的な パフォーマンス	${\displaystyle O(n^{2})}$ 比較、交換${\displaystyle O(n^{2})}$
最悪の場合の 空間複雑度	${\displaystyle O(n)}$ 合計、補助${\displaystyle O(1)}$
最適	いいえ

バブルソート（シンキングソートとも呼ばれる）は、入力リストの要素を一つずつ繰り返し処理し、現在の要素と次の要素を比較して、必要に応じて値を入れ替えるシンプルなソートアルゴリズムです。この処理は、リスト全体にわたって入れ替えがなくなるまで繰り返され、リストが完全にソートされた状態になります。このアルゴリズムは比較ソートと呼ばれ、大きな要素がリストの先頭に「バブル」していく様子からその名が付けられています。

実用的にはパフォーマンスが低く、主に教育ツールとして使用されています。PythonやJavaなどの一般的なプログラミング言語に組み込まれているソートライブラリでは、クイックソート、ティムソート、マージソートといったより効率的なアルゴリズムが使用されています。^{[2] [3]}

歴史

バブルソートアルゴリズムの最も古い記述は、数学者であり保険数理士でもあるエドワード・ハリー・フレンドによる1956年の論文^[4] 「電子計算機システムにおけるソート」^[5]で、 「ソート交換アルゴリズム」としてJournal of the Association for Computing Machinery (ACM)第3巻第3号に掲載されました。フレンドはこのアルゴリズムの基礎を説明しましたが、当初は注目されませんでしたが、数年後、現在の名称を命名したケネス・E・アイバーソンを含む多くの計算機科学者によって再発見されました。

分析

バブルソートの例。リストの先頭から始めて、隣接するすべてのペアを比較し、順序が間違っている場合（後者が前者より小さい場合）、位置を入れ替えます。各反復処理の後、比較する要素がなくなるまで、比較する要素が1つ（最後の要素）減ります。

パフォーマンス

バブルソートの最悪ケースおよび平均複雑度は です（はソート対象のアイテム数）。実用的なソートアルゴリズムのほとんどは、最悪ケースまたは平均複雑度が よりも大幅に低く、多くの場合 です。挿入ソートなどの他のソートアルゴリズムでさえ、一般的にバブルソートよりも高速に実行され、複雑さもそれほど変わりません。このため、バブルソートは実際にはほとんど使用されません。 ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n^{2})}$

挿入ソートと同様に、バブルソートは適応型であるため、クイックソートなどのアルゴリズムよりも優位性があります。つまり、平均的なケースではバブルソートよりも計算時間計算量が少ないにもかかわらず、リストが既にほぼソートされている場合（反転が少ない場合）、バブルソートはクイックソートなどのアルゴリズムよりも優れたパフォーマンスを発揮する可能性があります。例えば、バブルソートは既にソート済みのリストに対して実行されますが、クイックソートは依然としてソート処理全体を実行します。 ${\displaystyle O(n)}$ ${\displaystyle O(n\log n)}$

ソート アルゴリズムは、アルゴリズムを実行する前にリストをチェックするだけで、事前にソートされたリスト上で作成できますが、ほぼソートされたリストでのパフォーマンスの向上を再現するのは困難です。 ${\displaystyle O(n)}$

ウサギとカメ

バブルソートのパフォーマンスは、ソート中に要素を移動しなければならない距離と方向によって決まります。これは、要素がさまざまな方向にさまざまな速度で移動するためです。リストの末尾に向かって移動しなければならない要素は、連続してスワップに参加できるため、すばやく移動できます。たとえば、リスト内で最大の要素はすべてのスワップで勝利するため、リストの先頭近くにあっても、最初のパスでソート位置に移動します。一方、リストの先頭に向かって移動しなければならない要素は、1 パスあたり 1 ステップより速く移動できないため、要素は先頭に向かって非常にゆっくりと移動します。最小の要素がリストの末尾にある場合、先頭に移動するにはパスを繰り返す必要があります。このため、これらのタイプの要素は、イソップ童話のウサギとカメの登場人物にちなんで、それぞれウサギとカメと名付けられています。 ${\displaystyle n-1}$

バブルソートの速度を向上させるため、タートルをなくす様々な取り組みがなされてきました。カクテルソートは双方向のバブルソートで、先頭から末尾まで移動した後、逆順に末尾から先頭へ移動します。タートルをかなりスムーズに移動させることができますが、最悪のケースの複雑さは依然として残ります。コームソートは、大きなギャップで区切られた要素を比較し、タートルを非常に高速に移動させた後、より小さなギャップへと進んでリストを滑らかにします。平均速度は、クイックソートなどのより高速なアルゴリズムに匹敵します。 ${\displaystyle O(n^{2})}$

ステップバイステップの例

数値の配列「5 1 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)、アルゴリズムはそれらを交換しません。

2回目のパス

（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 4 5 8）

配列は既にソートされていますが、アルゴリズムはそれが完了したかどうかを把握していません。ソートされていると判断するには、スワップ処理を 行わずにさらに1回のパスを実行する必要があります。

3回目のパス

（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 ベースの配列):

手順bubbleSort ( A :ソート可能な項目のリスト) n := length ( A ) repeat swapped := false for i := 1 to n - 1 inclusive do { if this pair is out of order } if A [ i - 1 ] > A [ i ] then { swapped and remember something changed } swap ( A [ i - 1 ] , A [ i ]) swapped := true end if end for until not swapped end procedure      
      
    
          
               
            
                
                
                 
                  
             
         
      
 

バブルソートの最適化

ステップバイステップのバブルソート

リセット 次のステップ

44

3

7

1

Aを比較するとA交換開始>以来継続中≯リストはソートされています

0

バブルソートアルゴリズムは、 n回目のパスでn番目に大きい要素が見つかり、それを最終位置に格納されることを観察することで最適化できます。これにより、内側のループはn回目 の実行時に最後のn − 1 個の項目を参照する必要がなくなります。

手順bubbleSort ( A :ソート可能な項目のリスト) n := length ( A ) repeat swapped := false for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) swapped := true end if end for n := n - 1 until not swapped end procedure      
      
    
          
                 
                  
                   
                  
             
         
            
      
 

より一般的には、1回のパスで複数の要素が最終位置に配置される場合があります。特に、各パスの後、最後のスワップ後のすべての要素はソートされるため、再度チェックする必要はありません。これにより多くの要素をスキップすることができ、最悪のケースの比較回数は約50%改善されます（スワップ回数は改善されません）。また、新しいコードが変数を包含するため、複雑さはほとんど増加しませんswapped。

これを擬似コードで実現するには、次のように記述します。

手順bubbleSort ( A :ソート可能な項目のリスト) n := length ( A ) repeat newn := 0 for i := 1 to n - 1 inclusive do if A [ i - 1 ] > A [ i ] then swap ( A [ i - 1 ] , A [ i ]) newn := i end if end for n := newn until n ≤ 1 end procedure      
      
    
          
                 
                  
                   
                  
             
         
          
       
 

カクテル シェーカー ソートなどの代替の修正では、隣接するアイテムを繰り返し比較して交換するという同じアイデアを維持しながら、バブル ソートのパフォーマンスを改善しようとします。

使用

バブルソート。リストは直交座標系にプロットされ、各点 ( x , y ) はインデックスxに値yが格納されていることを示します。次に、リストは各ピクセルの値に従ってバブルソートによってソートされます。最も大きい要素が最初にソートされ、小さい要素は正しい位置に移動するのに時間がかかることに注意してください。

バブルソートは理解と実装が最も簡単なソートアルゴリズムの一つですが、O ( n^ ² )の計算量であるため、要素数が少なすぎるリストでは効率が劇的に低下します。単純なO ( n^ ² )ソートアルゴリズムの中でも、挿入ソートのようなアルゴリズムの方が通常ははるかに効率的です。

バブルソートは、その単純さから、コンピュータサイエンスの入門者に対し、アルゴリズム、あるいはソートアルゴリズムの概念を紹介する際によく用いられます。しかし、オーウェン・アストラチャンをはじめとする一部の教育者は、バブルソートとそのコンピュータサイエンス教育における継続的な人気を痛烈に批判し、もはや教えるべきではないと提言しています。^[6]

ジャーゴン・ファイルでは、ボゴソートを「典型的な、ひどくひどいアルゴリズム」と呼んでいますが、バブルソートも「一般的に悪いアルゴリズム」と呼んでいます。^[7] ドナルド・クヌースは、 『 The Art of Computer Programming』の中で、「バブルソートには、キャッチーな名前と、いくつかの興味深い理論的問題を引き起こすという事実以外に、推奨できる点は何もないようだ」と結論付け、そのいくつかについて論じています。^[8]

バブルソートは、最悪のケースでは挿入ソートと実行時間が漸近的に同等ですが、必要なスワップ回数は大きく異なります。Astrachanなどの実験結果では、ランダムリストであっても挿入ソートの方がはるかに優れた性能を示すことが示されています。これらの理由から、多くの現代のアルゴリズムの教科書では、バブルソートアルゴリズムではなく挿入ソートが採用されています。

バブルソートは現代のCPUハードウェアとの相性も悪い。挿入ソートに比べて書き込み回数が少なくとも2倍、キャッシュミスも2倍、そして分岐予測ミスも漸近的に増加する。^{[要出典] Astrachanによる}Javaでの文字列ソート実験では、バブルソートは挿入ソートの約5分の1、選択ソートの70%の速度であることが示された。^[6]

コンピュータグラフィックスにおいて、バブルソートは、ほぼソートされた配列における非常に小さなエラー（例えば、たった2つの要素の入れ替えなど）を検出し、線形計算量（2 n）で修正できることから広く利用されています。例えば、ポリゴンの塗りつぶしアルゴリズムでは、境界線は特定のスキャンライン（ x軸に平行な線）におけるx座標でソートされ、 y軸の増分に応じて、2つの線の交点においてのみ順序が変わります（2つの要素が入れ替わります）。バブルソートは、挿入ソートと同様に、安定したソートアルゴリズムです。

バリエーション

• 奇数-偶数ソートは、メッセージ パッシング システム用のバブル ソートの並列バージョンです。
• パスは左から右ではなく、右から左へ実行できます。これは、リストの末尾にソートされていない項目が追加される場合に効率的です。
• カクテル シェーカー ソートは、左方向と右方向のパスを交互に行います。

名前をめぐる議論

バブルソートは「沈み込みソート」と呼ばれることもある。^[9]

例えば、ドナルド・クヌースは、値を目的の位置またはその方向に挿入することを「[値]を適切なレベルに落ち着かせる」ことと表現し、「この分類方法は、ふるい分け法または沈下法と呼ばれることもある」と述べています。^[10]

この議論は、このアルゴリズムを 2 つの異なるが同等に有効な観点から簡単に検討できるため、永続化しています。

1. 大きな値はより重いとみなされ、リストの下部に徐々に沈んでいくと考えられる。
2. 値が小さいほど軽いとみなされ、リストの一番上に徐々に上がってくるように見える場合があります。

大衆文化において

2007年のインタビューで、元Google CEOのエリック・シュミットは当時大統領候補だったバラク・オバマに100万個の整数をソートする最良の方法について尋ねた。オバマは少し間を置いてからこう答えた。「バブルソートは間違った方法だと思います。」^{[11] [12]}

注記

1. Cortesi, Aldo (2007年4月27日). 「ソートアルゴリズムの視覚化」 . 2017年3月16日閲覧。
2. "[JDK-6804124] (coll) java.util.Arrays.sort の "modified mergesort" を timsort に置き換える - Java Bug System". bugs.openjdk.java.net . 2020年1月11日閲覧。
3. Peters, Tim (2002-07-20). 「[Python-Dev] ソート」 . 2020年1月11日閲覧。
4. 「エドワード・フレンド死亡記事（2019年） - ワシントンD.C. - ワシントン・ポスト」Legacy.com。
5. フレンド、エドワードH. (1956). 「電子計算機システムにおけるソート」. ACMジャーナル. 3 (3): 134– 168. doi : 10.1145/320831.320833 . S2CID  16071355.
6. Astrachan, Owen (2003). 「バブルソート：考古学的アルゴリズム分析」（PDF） . ACM SIGCSE Bulletin . 35 (1): 1– 5. doi :10.1145/792548.611918. ISSN  0097-8418.
7. 「jargon、ノード：bogo-sort」。www.jargon.net。
8. ドナルド・クヌース著『コンピュータプログラミングの芸術』第3巻：ソートと検索、第2版。アディソン・ウェズレー、1998年。ISBN 0-201-89685-0セクション5.2.2「交換によるソート」の106～110ページ。「[バブルソートを分析するための]計算に使用された手法は有益ではあるものの、結果は残念なものでした。なぜなら、バブルソートは実際にはそれほど優れているわけではないからです。[…] 単純な挿入法と比較すると、バブルソートはより複雑なプログラムを必要とし、約2倍の時間がかかります！」（1973年初版からの引用）
9. Black, Paul E. (2009年8月24日). 「バブルソート」.アルゴリズムとデータ構造の辞書.米国国立標準技術研究所. 2014年10月1日閲覧。
10. ドナルド・クヌース（1997年）『コンピュータプログラミングの芸術：第3巻：検索とソート』アディソン・ウェズレー社、p.80、ISBN 0201896850。
11. Lai Stirland, Sarah (2007年11月14日). 「オバマ氏、Google面接に合格」. Wired . 2020年10月27日閲覧。
12. バラク・オバマ、エリック・シュミット (2007年11月14日). Barack Obama | Candidates at Google (動画) (YouTube). Mountain View, CA 94043 The Googleplex: Talks at Google. イベントは23時20分に発生。2019年9月7日時点のオリジナルよりアーカイブ。 2019年9月18日閲覧。

参考文献

• Thomas H. Cormen 、 Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7問題2-2、40ページ。
• 分岐予測とキャッシュの存在下でのソート
• データ構造の基礎（エリス・ホロウィッツ、サルタジ・サーニ、スーザン・アンダーソン＝フリード著） ISBN 81-7371-605-6
• オーウェン・アストラチャン著『バブルソート：考古学的アルゴリズム分析』

外部リンク

• Martin, David R. (2007). 「アニメーションソートアルゴリズム：バブルソート」. 2015年3月3日時点のオリジナルよりアーカイブ。– グラフィカルなデモンストレーション
• 「ラフォーレのバブルソート」。2008年1月19日時点のオリジナルよりアーカイブ。2006年2月25日閲覧。（Javaアプレットアニメーション）
• OEISシーケンスA008302（ソート中にk回のペア交換を必要とする[n]の順列の数の表（統計））