「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

順番に見ていきましょう。
まずは予備知識として「ソート」について簡単に説明します。
「そんなの説明されなくても知ってるよ！」な人は適当に読み飛ばしてください。

ソートは「何らかの規則に従ってデータを並べること」です。
並べる順番は

・小さい順（昇順）
・大きい順（降順）
・アルファベット順
・五十音順
・古い順
・新しい順
・好きな順
・嫌いな順

など、いろいろ あります。



以上を踏まえて、本題に入ります。

データを小さい順（昇順）、もしくは大きい順（降順）に並べたいとしましょう。

いろいろな やり方があります。

その「いろいろな やり方」のひとつで

隣り合う要素の大小比較と並べ替えを繰り返して、全体を並べ替えるやり方

が「バブルソート」です。

……と言われても、ピンと来ないですよね。

大丈夫です。
例を挙げて説明します。

なお、先に理屈だけ書いておくと

１．1つ目の値と2つ目の値を比較する
２．1つ目が大きければ、左右を入れ替える
３．次に2つ目の値と3つ目の値を比較する
４．2つ目が大きければ、左右を入れ替える
５．同じことを3つ目以降も繰り返すと、最終的に1番大きな値が1番右側に来る
６．再度１から４の手順を繰り返す
７．2番目に大きな値が右から2番目に来る
８．再度１から４の手順を繰り返す
９．3番目に大きな値が右から3番目に来る
１０．これを全要素が並ぶまで繰り返す

です。

文字だけで見ても、よく分からないと思います。
今の時点では理解できなくてOKです。
気が向いたら、最後まで読んだ後に見返してください。

それでは、見ていきましょう。

例えば、以下の4つの数字があったとします。
これを小さい順に並べ替えます。

3、2、1、4

バブルソートでは、まず一番左の値「3」に注目します。
仮に これを「要素1」と呼びましょう。



ついでなので、左から2番目の値「2」は「要素2」ということにします。
同様に左から3番目の値「1」は「要素3」です。
左から4番目、一番右の値「4」は「要素4」になります。



バブルソートで最初にやるのは、要素1と要素2の比較です。



もし要素1の方が大きければ、要素2と左右を入れ替えます。
小さい順に並べる場合は、

常に右の方が大きくなるようにする

のです。
ちなみに、大きい順に並べるときは逆です。
右の方が小さくなるようにします。

さて、今回の例では、要素1は「3」です。
要素2は「2」です。
左の要素1の方が大きいですね。



右の方を大きくしたいので、要素1と要素2を入れ替えます。



次は、要素2と要素3の比較です。
要素2には、先ほど入れ替えた「3」が入っています。
要素3は「1」です。



また、左の要素2の方が大きいですね。
要素2と要素3を入れ替えます。



次に、要素3と要素4の比較です。
要素3には、先ほど入れ替えた「3」が入っています。
要素4は「4」です。



これは最初から右の方が大きいです。
要素の入れ替えはやりません。
そのままにしておきましょう。



次は要素4と要素5……は ないので、一旦 終了です。
この時点で、並びは以下のようになっています。

2、1、3、4

一番右側の要素が一番大きい値になっていますね。



小さい順に並べるということは、一番右側には一番大きな値が来ます。
実際に今、一番右側に一番大きな値が来ています。
ということは、一番右側は、これで確定としてしまって良いでしょう。

要素4の値は「4」で確定です。



次に、まだ確定していない要素

2、1、3

に対して、同じことをやります。



要素1は「2」です。
要素2は「1」です。
左の方が大きいので、入れ替えます。



入れ替えた後の要素2は「2」です。
要素3は「3」です。
右の方が大きいので、そのままにしておきます。



これで、残りの要素の中で一番大きい値「3」が（残りの要素の中で）一番右に来ました。



要素3の値は「3」で確定です。



次に、まだ確定していない要素

1、2

に対して、同じことをやります。



あぁ、これは何もしなくて大丈夫ですね。
この時点で、要素1の値は「1」で、要素2の値は「2」で確定します。

全体は

1、2、3、4

になりました。
ちゃんと、小さい順に並んでいます。



このような

隣接する要素の大小比較と入れ替えを繰り返すことで昇順（降順）に並べ替えるやり方

が、バブルソートです。

カッコつけて言うと

値を昇順・降順で並べ替えるアルゴリズムのひとつ

ですかね。
アルゴリズムは「考え方」や「やり方」と解釈してください。

……というのが、バブルソートの教科書的な説明です。
バブルソートの説明を読むと、九割がた、似たような例が書いてあると思います。

説明が画一的になるのは、最終的な目的がプログラムを作ることだからです。

ぶっちゃけ、バブルソートの処理の書き方って決まり文句みたいなものなのですね。
「バブルソート　サンプル　【プログラミング言語の種類（Javaとか）】」を検索キーワードにしてGoogleとかYahoo!で検索すれば、サンプルが腐るほど見つかります。

その処理を日本語に直したのが、ここまでに書いたような説明なのです。
バブルソートの処理の書き方なんて似たりよったりです。
そのため、バブルソート自体の説明も似たりよったりになります。

とはいえ、そんな説明に対して「よく分からない」な人もいるでしょう。
そんな人に向けて、ちょっと目先を変えた説明も書いておきますね。

ただし、あくまでイメージをつかむための説明です。
実際のプログラムを作るときは、上に書いたような説明も頑張って理解してください。

それでは始めます。

ある日のことです。
ピヨ太君が川で洗濯をしていると、上からミカン箱が流れてきました。



ピヨ太君はミカン箱を拾います。

なんと！
ミカン箱にはミカンが3個入っていました。



おっと、またミカン箱が流れてきました。
ピヨ太君は貧弱なので、2つは持って帰れません。
今持っているミカン箱か、流れてきたミカン箱か、どちらかを選ぶ必要があります。



上から覗き見たところ、流れてきたミカン箱には、ミカンが2個入っていました。
今持っているミカン箱の方が、ミカンがいっぱい入っています。

ピヨ太君は、流れてきたミカン箱をスルーしました。



おっと、またミカン箱が流れてきました。



上から覗き見たところ、流れてきたミカン箱には、ミカンが1個入っていました。
今持っているミカン箱の方が、ミカンがいっぱい入っています。

ピヨ太君は、流れてきたミカン箱をスルーしました。



おっと、またミカン箱が流れてきました。



上から覗き見たところ、流れてきたミカン箱には、ミカンが4個入っていました。
今持っているミカン箱よりも、ミカンがいっぱい入っています。

ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。



どうやらミカン箱は、もう流れてこないようです。
ピヨ太君は、ミカンが4個入ったミカン箱をお家に持って帰りました。



ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻りました。



おっと、先ほどスルーしたミカン箱が流れてきたようです。
ミカンが2個入っています。



ピヨ太君は、ミカン箱を拾いました。



おっと、またミカン箱が流れてきました。
ミカンが1個入っています。



今、持っている方がいっぱい入っていますね。
スルーしましょう。



おっと、またミカン箱が流れてきました。
ミカンが3個入っています。



流れてきたミカン箱の方が、ミカンがいっぱい入っています。
ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。



ミカン箱は、もう流れてきません。
ピヨ太君は、ミカンが3個入ったミカン箱をお家に持って帰りました。



ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻ります。



ミカン箱が流れてきました。
ミカンが1個入っています。



とりあえず拾っておきましょう。



おっと、またミカン箱が流れてきました。
ミカンが2個入っています。



流れてきたミカン箱の方が、ミカンがいっぱい入っています。
ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。



ミカン箱は、もう流れてきません。
ピヨ太君は、ミカンが2個入ったミカン箱をお家に持って帰りました。



ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻ります。



そして、ミカンが1個入ったミカン箱も回収してきました。



これでピヨ太君のお家には、ミカン箱が4つあります。
しかも、部屋の奥に行くほど、たくさんのミカンが入ったミカン箱です。



部屋の手前から、小さい（ミカンが少ない）順に並んでいますよね？

これがバブルソートのイメージです。

今持っている要素と後から来た要素を比較して、後から来た要素の方が大きければ、持ち替えます。
それを繰り返すと、すべての要素が通過した時点で、手元には一番大きな要素が残ります。
一番大きな要素を取り除いて、残った要素に対して同じ手順をやります。
繰り返すと、大きな要素から取り除かれていって、最終的に一番小さな要素が残ります。
取り除いた要素を逆に辿ると、小さい順に並んでいる理屈です。

実際のところ、マジメな説明も、ミカン箱の説明も、やっていることは同じです。

観測対象が固定で観測位置が移動すると解釈したのが、真面目な説明です。



観測位置が固定で観測対象が移動すると解釈すると、ミカン箱の説明になります。



最初は、イメージしやすい方で覚えてください。
どちらもイメージしにくい場合は……もっと説明の上手い人のところで勉強してください。けっ！