バブルソートの仕組みを徹底解説！アニメーションで学ぶ「ひたすら比較・交換」ソート・単純交換【ソートアルゴリズム入門】#3

単純ソート３種のうちの一つ”バブルソート”

ソートアルゴリズムのうち、単純な並び替えでソート(並び替え)を行うものとして、挿入ソート・バブルソート・選択ソートがあり、これらを単純ソートと呼びます。

バブルソートの実行例　アニメーション

（※このほかにも、比較的低性能なソートを単純ソートと呼ぶ場合がある)

バブルソートは、入れ替え中の最大値が炭酸の泡のように少しずつ上に上がっていく様子からバブル(泡)ソートと呼ばれているソートアルゴリズムです。バブルソートのキモは「隣同士をひたすら比較・交換」し、結果として「重い（大きい）要素が沈み、軽い（小さい）要素が泡（Bubble）のように浮かび上がる」というイメージです。

今回は、入れ替え途中が面白い、バブルソートについて、自動探索アニメーション付きのツールで学んでいきましょう。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...

1. バブルソート（Bubble Sort・単純交換法）とは？

選択ソート（最大値選択法）は、以下のステップを繰り返すアルゴリズムです。

1. バブルソートは、「隣り合う要素の比較と交換」を繰り返すアルゴリズムです。
2. まず、配列の先頭（1番目と2番目）を比較します。
3. もし順序が逆（例：昇順なら、1番目 > 2番目）なら、2つを交換 (Swap) します。
4. 次に、1つずれて（2番目と3番目）を比較し、逆順なら交換します。
5. これを配列の最後まで繰り返します。この操作（1周目のパス）が終わると、配列の中で一番大きな値が、必ず一番右端（末尾）に移動します。
6. これで、末尾の要素は「確定（ソート済み）」となります。
7. 次に、残りの「未ソート領域」（配列の先頭から末尾-1まで）に対して、再び 1. から 4. を繰り返します。
8. 未ソート領域がなくなるまでこれを続けると、全体が整列されます。
9. 一番大きな（重い）要素が、比較のたびに右へ右へと移動し、まるで水底に沈んでいくように見えるのが特徴です。

2. バブルソートの動きを見てみよう！

選択ソートで並び替えを試せます。ステップ実行ボタンを押して、並び替えを進めてみてください。

バブルソートの疑似コード(ソートの手順)

手元で試せる環境があったら自身の慣れているプログラミング言語で以下の処理を書いてみると理解が深まると思います。

algorithm BubbleSort(L) is
  n ← length of L
  
  // i: パス回数 (0 から n-2 まで)
  // (iが増えるほど、末尾のソート済み領域が増える)
  for i from 0 to n-2 do
    
    // このパスで交換が発生したかどうかのフラグ
    swapped ← false 
    
    // j: 比較インデックス (0 から n-2-i まで)
    // (n-1-i が未ソート領域の末尾)
    for j from 0 to n-2-i do
      
      // もし (左 > 右) なら交換
      if L[j] > L[j+1] then
        temp ← L[j]
        L[j] ← L[j+1]
        L[j+1] ← temp
        swapped ← true // 交換が発生した
      end
      
    end
    
    // もしこのパスで一度も交換がなければ、ソート完了
    if swapped = false then
      break // 外側のループ (i) を抜ける
    end
    
  end
  
  return L
end

まとめ

• バブルソートは、「隣り合う要素を比較し、逆順なら交換する」を繰り返すアルゴリズム。
• 1周するごとに、最大値が末尾に確定（沈んで）いく。

ここまでの３回で単純ソートの仕組みについて学んできました、次回では、単純ソートの計算量について、そもそも計算量って何？というところから、ちょっとだけ数学的に踏み込んでみようと思います。中学生でもわかるようにまとめてあるので、あまり気負いせず見ていってもらえると幸いです。

計算量 とは？データ数が倍になると手間が4倍？単純ソートの計算量O[n^2]を中学生でもわかるように解説【ソートアルゴリズム入門】#4

なぜ単純ソートはデータが増えると遅くなる？その「遅さ」を測るモノサシが「計算量」と「O記法」です。この記事では、O(n^2) といった計算量の考え方を、中学生でもわかる「作業の手間」に例えて解説。グラフで「増え方の勢い」を学び、次の高速なアルゴリズムへ進みましょう。

ほかの単純ソートをもっと知りたい方は過去の記事へどうぞ。

11 記事

シリーズ

ソートアルゴリズム

ソートアルゴリズムについて、単純ソート、分割統治法などの比較するソート、基数ソートなどの比較しないソートまでその仕組みを...