交換法とは、隣り合ったデータ同士を比較し、並び順が逆であれば交換する操作を繰り返す方法です。別名「バブルソート」とも呼ばれます。
交換法ではどのようにデータが並び替えられるか見てみましょう。
情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-10
実践プログラム③ 整列アルゴリズム 交換法
4. 交換法とは ( 4 / 12 )
交換法(バブルソート)とは
学習の目的
-
1. 交換法(バブルソート)とは
-
2. 交換法の手順
-
3. 交換法の流れの確認
1. 交換法(バブルソート)とは
2. 交換法の手順
次の5つのデータを交換法で昇順に並び替える例を見ていきましょう。
①一番大きな要素の確定
①-1.左端と右隣の要素を比較する
左端(data[0])と右隣(data[1])の要素を比較します。
この二つを見たとき、昇順になっていないため、交換します。
交換法は、必ず隣同士の要素で比較を行います。 比較の結果が昇順になっていなければ交換をします。
①-2.比較する隣同士の組を1つ右へ
data[1]とdata[2]を比較します。
ここは昇順になっている(右が大きい)ので、交換はしません。
①-3.比較する隣同士の組を1つ右へ
data[2]とdata[3]を比較します。
ここは昇順になっていない(左が大きい)ので、交換します。
①-4.比較する隣同士の組を1つ右へ
data[3]とdata[4]を比較します。
ここは昇順になっていない(左が大きい)ので、交換します。
この段階で、すべての隣接データの比較が終わりました。
すべての値との比較が終わると、一番右の位置のデータが確定します。(最大値が右に行く)
隣同士を比較して交換していくから、大きい値がどんどん右の方へ行くんですね。
結果的に一番大きい値が、一番右に行くのか。
でも、まだ整列は完了していませんよね。
一番右のデータが確定したので、残ったデータで同じことを行い、大きい値から確定させていきます。
続けて見てましょう。
②二番目に大きな要素の確定
②-1.左端と右隣の要素を比較する
左端(data[0])と右隣(data[1])の要素を比較します。
ここは昇順になっている(右が大きい)ので、交換はしません。
②-2.比較する隣同士の組を1つ右へ
data[1]とdata[2]を比較します。
ここは昇順になっていない(左が大きい)ので、交換します。
②-3.比較する隣同士の組を1つ右へ
data[2]とdata[3]を比較します。
ここは昇順になっていない(左が大きい)ので、交換します。
未確定部分の比較が完了しました。この中の最大値がdata[3]にいき、ここが確定します。
③三番目に大きな要素の確定
③-1.左端と右隣の要素を比較する
左端(data[0])と右隣(data[1])の要素を比較します。
ここは昇順になっていない(左が大きい)ので、交換します。
③-2.比較する隣同士の組を1つ右へ
data[1]とdata[2]を比較します。
ここは昇順になっている(右が大きい)ので、交換しません。
未確定部分の比較が完了しました。この中の最大値がdata[2]にいき、ここが確定します。
④四番目に大きな要素の確定
④-1.左端と右隣の要素を比較する
左端(data[0])と右隣(data[1])の要素を比較します。
ここは昇順になっている(右が大きい)ので、交換はしません。
未確定部分の比較が完了しました。この中の最大値がdata[1]にいき、ここが確定します。
ここで、未確定要素は残り1つですが、他のデータの並びが決まったので最後の一つも自動的に決まることになり、並び替えが完了しました。
右から順に確定するんですね。
3. 交換法の流れの確認
今の手順をもう一度ツールを使って確認しましょう。再生ボタンをクリックして、比較と交換の流れを確認しましょう。
コ
ラ
ム
バブルソートという名前の由来
私たちが学んだ「交換法（バブルソート）」には、ちょっと面白い名前の由来があります。
「バブル（bubble）」とは 泡 のこと。
お風呂の中で泡が上へ上へと浮かんでいく様子を思い出してください。
バブルソートでも、大きい値（数字）が比較と交換をくり返すうちに、だんだん右の方へ移動していく 様子が、まるで泡が水面へと浮かんでいくように見えるのです。
この動きが「泡が浮かぶ＝bubble up」に似ていることから、
このアルゴリズムは “Bubble Sort（バブルソート）” と呼ばれるようになりました。
イメージで覚えよう！
・小さい値は下に沈み、
・大きい値は交換をくり返しながら「浮かんでいく」
・だから 泡のように上がる → バブルソート！
