情報処理技術者試験対策 > アルゴリズム > バブルソート

バブルソートについての説明

バブルソートとは、一番左から、隣どおしの数を比べて、大きいほうを右側に持ってくる、ということをこれを一番右に行くまで繰り返すアルゴリズムをいいます。

バブルソートは情報処理技術者試験などの教科書にも必ず出てくるアルゴリズムで、一番単純であるものの、通常は一番効率が悪い例として登場してきます。

具体的なソートは下記のように行われます。

  1. 一番左から、隣どおしの数を比べて、大きいほうを右側に持ってくる→これを一番右に行くまで繰り返す。
  2. 再度一番左から、隣どおしの数を比べて、大きいほうを右側に持ってくる→これを右から2番目に行くまで繰り返す。
  3. 1番と2番を延々繰り返す。

今回は、下のような適当に並んでいる数字を、右のように並べ替える、というのを例にして考えていきたいと思います。

3 5 4 2 8 1 6 9 7 → 1 2 3 4 5 6 7 8 9

バブルソートのアルゴリズム 具体例

1巡目

ソート1巡目

左から順番に2つの数字を比較していっています。比較の結果、数字の順番を入れ替えるべき場所(Xマークが書かれているところ)で数字の順番が入れ替わり、右側の数字が大きくなっているのがわかるでしょうか?

結局、1巡目の終わりでは、一番大きい数字(9)が一番右に来ています。

2巡目

ソート2巡目

また、左から順番に2つの数字を比較していっています。比較の結果、数字の順番を入れ替えるべき場所(Xマークが書かれているところ)で数字の順番が入れ替わっています。

なお、一番右は既に、1巡目終了時点で、並べ替えが完了しているため、その手前までを並べ替えていきます。


注:上の例では、偶然、2巡目が終わった時点で、右の5つの数字がきちんと並べ替えられています(一番右が5 6 7 8 9 となっていますね)。でも、一般的には、2巡目が終わった時点で、順序が正しくなっていることが保証されているのは、右から2つ目の数字までです。そのため、上のような場合でも、3巡目は、一番左の数字から、右から3つ目の数字までを並べ替えていくことになります。


カテゴリ一覧
アルゴリズム
アルゴリズムとは  ソートアルゴリズム  バブルソート  インサーションソート  クイックソート  マージソート  ソートアルゴリズムを体感する