[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

バブルソート (bubble sort)

pointこの用語のポイント

point並べ替えのやり方だよ

point昇順 or 降順に並べたいときに使うよ

point隣り合う要素の大小比較を繰り返すことで、全体を並べ替えるよ

スポンサーリンク

簡単に書くよ

バブルソート (bubble sort)とは

データを昇順 or 降順に並べ替える際の、やり方のひとつ
であり

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

image piyo

詳しく書くよ

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

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

その「いろいろなやり方」のひとつが「バブルソート」です。
バブルソートでは隣り合う要素の大小比較と並べ替えを繰り返して、全体を並べ替えます。

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

実際の例を見ながら、説明していきます。

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

1.1つ目の値と2つ目の値を比較する
2.1つ目が大きければ、左右を入れ替える
3.次に2つ目の値と3つ目の値を比較する
4.2つ目が大きければ、左右を入れ替える
5.同じことを3つ目以降も繰り返すと、最終的に1番大きな値が1番右側に来る
6.再度1から4の手順を繰り返す
7.2番目に大きな値が右から2番目に来る
8.再度1から4の手順を繰り返す
8.3番目に大きな値が右から3番目に来る
9.これを全要素が並ぶまで繰り返す


です。

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

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

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

3、2、1、4

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

バブルソート

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

バブルソート2

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

バブルソート3

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

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

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

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

バブルソート4

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

バブルソート5

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

バブルソート6

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

バブルソート7

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

バブルソート8

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

バブルソート9

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

2、1、3、4

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

バブルソート10

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

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

バブルソート11

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

2、1、3

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

バブルソート12

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

バブルソート13

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

バブルソート14

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

バブルソート15

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

バブルソート16

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

1、2

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

バブルソート17

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

全体は

1、2、3、4

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

バブルソート18

このような

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

が、バブルソートです。

カッコつけて言うと

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

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

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

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

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

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

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

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

それでは、始めます。

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

バブルソート19

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

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

バブルソート20

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

バブルソート21

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

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

バブルソート22

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

バブルソート23

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

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

バブルソート24

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

バブルソート25

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

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

バブルソート26

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

バブルソート27

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

バブルソート28

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

バブルソート29

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

バブルソート30

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

バブルソート31

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

バブルソート32

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

バブルソート33

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

バブルソート34

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

バブルソート35

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

バブルソート36

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

バブルソート37

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

バブルソート38

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

バブルソート39

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

バブルソート40

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

バブルソート41

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

バブルソート42

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

バブルソート43

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

バブルソート44

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

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

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

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

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

バブルソート45

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

バブルソート46

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

image piyo2

一言でまとめるよ

まぁ「バブルソート」って単語が出てきたら「並べ替えのやり方なんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク