バブルソート

バブルソート

バブルソートの静的可視化[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]} ただし、並列処理が許可されている場合、バブルソートはO(n)時間でソートするため、並列化がそれほど効果的ではない挿入ソートや選択ソートの並列実装よりも大幅に高速になります。^[要出典]

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

バブル ソートの最悪ケースおよび平均複雑度は で、 はソートされる項目の数です。ほとんどの実用的なソート アルゴリズムは、最悪ケースまたは平均複雑度が大幅に改善され、多くの場合 です。挿入ソートなどの他のソート アルゴリズムでも、一般にバブル ソートよりも高速に実行され、複雑さは変わりません。このため、バブル ソートは実際にはほとんど使用されません。 ${\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      
      
    
          
               
            
                
                
                 
                  
             
         
      
 

バブルソートアルゴリズムは、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手順      
      
    
          
                 
                  
                   
                  
             
         
            
      
 

より一般的には、1 回のパスで複数の要素が最終位置に配置されることがあります。特に、各パスの後に、最後の swap 後のすべての要素がソートされ、再度チェックする必要はありません。これにより、多くの要素をスキップすることができ、最悪の場合の比較回数が約 50% 改善されます (swapped 回数は改善されません)。また、新しいコードが "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手順      
      
    
          
                 
                  
                   
                  
             
         
          
       
 

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

バブルソートは理解と実装が最も簡単なソートアルゴリズムの 1 つですが、そのO ( n ² )の複雑性により、少数以上の要素を含むリストでは効率が大幅に低下します。単純なO ( n ^{2 ) ソートアルゴリズムの中でも、}挿入ソートなどのアルゴリズムの方が通常ははるかに効率的です。

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

Jargon File では、ボゴソートを「典型的なひどいアルゴリズム」と呼んで有名ですが、バブルソートも「一般的な悪いアルゴリズム」と呼んでいます。 ^[7] Donald Knuthは、 The Art of Computer Programmingで、「バブルソートには、キャッチーな名前と、興味深い理論的問題を引き起こすという事実以外には、推奨できる点が何もないように思われる」と結論付け、そのいくつかについて論じています。^[8]

バブル ソートは、最悪の場合、実行時間では挿入ソートと漸近的に同等ですが、必要なスワップの数は 2 つのアルゴリズムで大きく異なります。Astrachan などの実験結果では、挿入ソートはランダム リストでもかなり優れたパフォーマンスを発揮することが示されています。これらの理由から、多くの現代のアルゴリズムの教科書では、バブル ソート アルゴリズムの使用を避け、挿入ソートを採用しています。

バブルソートは、現代のCPUハードウェアとの相互作用も悪い。挿入ソートに比べて少なくとも2倍の書き込み、2倍のキャッシュミス、そして漸近的に分岐予測ミスが多く発生する。^[要出典] Javaで文字列をソートするAstrachanの実験では、バブルソートは挿入ソートの約5分の1、選択ソートの70％の速度であることがわかった。^[6]

コンピュータグラフィックスの分野では、バブルソートは、ほぼソートされた配列内の非常に小さなエラー（2 つの要素の入れ替えなど）を検出し、線形複雑度（2 n）のみで修正できることから人気があります。たとえば、ポリゴンの塗りつぶしアルゴリズムで使用されます。このアルゴリズムでは、境界線は特定のスキャンライン（ x軸に平行な線）のx座標でソートされ、 y が増分すると、2 つの線の交点でのみ順序が変わります（2 つの要素が入れ替わります）。バブルソートは、挿入ソートのような安定したソートアルゴリズムです。

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

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

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

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

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

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

• トーマス・H・コーメン、チャールズ・E・ライザーソン、ロナルド・L・リベスト、クリフォード・スタイン。アルゴリズム入門、第 2 版。 MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7。問題2-2、40ページ。 
• 分岐予測とキャッシュがある場合のソート
• データ構造の基礎、Ellis Horowitz、Sartaj Sahni、Susan Anderson-Freed 著、ISBN 81-7371-605-6 
• オーウェン・アストラチャン「バブルソート：考古学的アルゴリズム分析」
• コンピュータ統合製造、Spasic博士、Srdic MSc、オープンソース、1987年[1]

Wikibookアルゴリズム実装には、バブルソートに関するページがあります。

ウィキメディア・コモンズには、バブルソートに関連するメディアがあります。

Wikiversityにはバブルソートに関する学習リソースがあります

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