バブルソートというのは、値の並びをソートする方法としては速いとは言えないものの、わかりやすいものの一つだと思います。そこで、バブルソートを例に、普通のやりかたと、普通はこうはやらないだろうという例を挙げてみます。

 

まず、バブルソートというのがどういうものかを簡単に。

[ 2, 8, 9, 5, 7 ] という、数値の並びがあるとします。これを昇順に並べ替える (ソート) したいとします。手順としては、隣り合う値を比べて、必要なら入れ替えるという方法です。

この場合、「2と8では8の方が大きいのでそのままま。8と9では9の方が大きいのでそのまま。9と5では9の方が大きいので、9と5を入れ替える」という手順で行ないます。この段階では、元の並びが、[ 2, 8, 5, 9, 7 ] と変わっています。以後同じように、入れ替えが起こらなくなるまで繰り返します。これが普通のやり方です。

これをPythonのコードで書くと、こんな感じになります:

data1 = [5, 9, 2, 1, 3, 7, 6, 4, 8]　# 並べ替えの対象となるデータ

for j in range(len(data1)-1):
　for i in range(len(data1)-1):
　　if i < len(data1) - 1 and data1[i] > data1[i+1]:　# A
　　　l = data1[i]
　　　data1[i] = data1[i+1]
　　　data1[i+1] = l
　print("Current", j, i, data1)
print("Result:", data1)

これを、ex2.pyという名前で保存して、実行すると、このような結果が得られます (上記コードは本来半角スペースを使うところを、活動報告の制限から全角スペースを使っている箇所があります)。

Current 0 0 [5, 9, 2, 1, 3, 7, 6, 4, 8]
Current 0 1 [5, 2, 9, 1, 3, 7, 6, 4, 8]
Current 0 2 [5, 2, 1, 9, 3, 7, 6, 4, 8]
Current 0 3 [5, 2, 1, 3, 9, 7, 6, 4, 8]
Current 0 4 [5, 2, 1, 3, 7, 9, 6, 4, 8]
Current 0 5 [5, 2, 1, 3, 7, 6, 9, 4, 8]
Current 0 6 [5, 2, 1, 3, 7, 6, 4, 9, 8]
Current 0 7 [5, 2, 1, 3, 7, 6, 4, 8, 9]
Current 1 0 [2, 5, 1, 3, 7, 6, 4, 8, 9]
Current 1 1 [2, 1, 5, 3, 7, 6, 4, 8, 9]
Current 1 2 [2, 1, 3, 5, 7, 6, 4, 8, 9]
Current 1 3 [2, 1, 3, 5, 7, 6, 4, 8, 9]
Current 1 4 [2, 1, 3, 5, 6, 7, 4, 8, 9]
Current 1 5 [2, 1, 3, 5, 6, 4, 7, 8, 9]
Current 1 6 [2, 1, 3, 5, 6, 4, 7, 8, 9]
Current 1 7 [2, 1, 3, 5, 6, 4, 7, 8, 9]
　[略]
Current 6 0 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 1 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 2 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 3 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 4 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 6 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 7 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 0 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 1 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 2 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 3 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 4 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 6 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 7 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

最後の “Result” の箇所で、昇順にならんでいることが確認出来ます。

なお、ご覧のとおりの無駄は、バブルソートが速くないことの一例です。

 

では、バブルソートはこのやりかたしか方法はないのでしょうか。たとえばこんなのはどうでしょう。

pat = [
　[[2, 1], [1, 2]],
　[[3, 1], [1, 3]],
　[[4, 1], [1, 4]],
　[[5, 1], [1, 5]],
　[[6, 1], [1, 6]],
　[[7, 1], [1, 7]],
　[[8, 1], [1, 8]],
　[[9, 1], [1, 9]],
　[[3, 2], [2, 3]],
　[[4, 2], [2, 4]],
　[[5, 2], [2, 5]],
　[[6, 2], [2, 6]],
　[[7, 2], [2, 7]],
　[[8, 2], [2, 8]],
　[[9, 2], [2, 9]],
　[[4, 3], [3, 4]],
　[[5, 3], [3, 5]],
　[[6, 3], [3, 6]],
　[[7, 3], [3, 7]],
　[[8, 3], [3, 8]],
　[[9, 3], [3, 9]],
　[[5, 4], [4, 5]],
　[[6, 4], [4, 6]],
　[[7, 4], [4, 7]],
　[[8, 4], [4, 8]],
　[[9, 4], [4, 9]],
　[[6, 5], [5, 6]],
　[[7, 5], [5, 7]],
　[[8, 5], [5, 8]],
　[[9, 5], [5, 9]],
　[[7, 6], [6, 7]],
　[[8, 6], [6, 8]],
　[[9, 6], [6, 9]],
　[[8, 7], [7, 8]],
　[[9, 7], [7, 9]],
　[[9, 8], [8, 9]]
]

data1 = [5, 9, 2, 1, 3, 7, 6, 4, 8]

for j in range(len(data1)-1):
　for i in range(len(data1)-1):
　　if i < len(data1) -1:
　　　data2 = [data1[i], data1[i+1]] 　# B
　　　for k in range(len(pat)):
　　　　if data2 == pat[k][0]: 　　　　# C
　　　　　data1[i] = pat[k][1][0]
　　　　　data1[i+1] = pat[k][1][1]
　　　　　print("FIND", data2, "->", pat[k][1])
　　　print("Current", j, i, data1)

print("Result:", data1)

これはなにをやっているかというと、まず、入れ替える並びと、それを入れ替えた結果を “pat” という変数に入れています。

また、“# B” のところで、並びの二つ組を作っており、“# C” のところでは、作った二つ組と “pat” の中身を比べています ( [[9, 8], [8, 9]] などの左側、つまり [9, 8] など)。さらに、“# C” の if文の中身で、並びの値を “pat” に基づいて書き換えています ( [[9, 8], [8, 9]] などの右側、つまり [8, 9] など)。

これを実行した結果を見てみましょう:

Current 0 0 [5, 9, 2, 1, 3, 7, 6, 4, 8]
FIND [9, 2] -> [2, 9]
Current 0 1 [5, 2, 9, 1, 3, 7, 6, 4, 8]
FIND [9, 1] -> [1, 9]
Current 0 2 [5, 2, 1, 9, 3, 7, 6, 4, 8]
FIND [9, 3] -> [3, 9]
Current 0 3 [5, 2, 1, 3, 9, 7, 6, 4, 8]
FIND [9, 7] -> [7, 9]
Current 0 4 [5, 2, 1, 3, 7, 9, 6, 4, 8]
FIND [9, 6] -> [6, 9]
Current 0 5 [5, 2, 1, 3, 7, 6, 9, 4, 8]
FIND [9, 4] -> [4, 9]
Current 0 6 [5, 2, 1, 3, 7, 6, 4, 9, 8]
FIND [9, 8] -> [8, 9]
Current 0 7 [5, 2, 1, 3, 7, 6, 4, 8, 9]
FIND [5, 2] -> [2, 5]
Current 1 0 [2, 5, 1, 3, 7, 6, 4, 8, 9]
FIND [5, 1] -> [1, 5]
Current 1 1 [2, 1, 5, 3, 7, 6, 4, 8, 9]
FIND [5, 3] -> [3, 5]
Current 1 2 [2, 1, 3, 5, 7, 6, 4, 8, 9]
Current 1 3 [2, 1, 3, 5, 7, 6, 4, 8, 9]
FIND [7, 6] -> [6, 7]
Current 1 4 [2, 1, 3, 5, 6, 7, 4, 8, 9]
FIND [7, 4] -> [4, 7]
Current 1 5 [2, 1, 3, 5, 6, 4, 7, 8, 9]
Current 1 6 [2, 1, 3, 5, 6, 4, 7, 8, 9]
Current 1 7 [2, 1, 3, 5, 6, 4, 7, 8, 9]
FIND [2, 1] -> [1, 2]
Current 2 0 [1, 2, 3, 5, 6, 4, 7, 8, 9]
Current 2 1 [1, 2, 3, 5, 6, 4, 7, 8, 9]
Current 2 2 [1, 2, 3, 5, 6, 4, 7, 8, 9]
Current 2 3 [1, 2, 3, 5, 6, 4, 7, 8, 9]
FIND [6, 4] -> [4, 6]
Current 2 4 [1, 2, 3, 5, 4, 6, 7, 8, 9]
Current 2 5 [1, 2, 3, 5, 4, 6, 7, 8, 9]
Current 2 6 [1, 2, 3, 5, 4, 6, 7, 8, 9]
Current 2 7 [1, 2, 3, 5, 4, 6, 7, 8, 9]
　[略]
Current 6 0 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 1 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 2 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 3 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 4 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 6 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 6 7 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 0 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 1 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 2 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 3 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 4 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 6 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current 7 7 [1, 2, 3, 4, 5, 6, 7, 8, 9]
Result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

ここで “FIND” とあるのは、“pat” にあるものが、対象に見つかったことを示しています。

そして、 “Result” にあるように、やはり並べ替え (ソート) ができています。 

２つのやり方を見ましたが、見た目は結構違います。大きな違いは、後者では「見つける並びと、その並べ替えのデータ」を定義していること。そして、前者では値の比較 (“# A” の箇所) と、入れ替えをやっているのに対して、後者では、“pat” の中身に一致するものを探し (“# C” の箇所)、“pat” の中身で置き換えていること。   この２つが大きな違いでしょう。

なお、「“pat” の中身を作るのは大変」と思われるかもしれませんが、それ自体もコンピュータに生成させればいいので、大した問題にはならないことも注意してください。

この例では、並べ替える対象は “[5, 9, 2, 1, 3, 7, 6, 4, 8]” という簡単なデータ構造でした。後者については、“pat” は３次元の配列になっていますが、とくに “[[2, 1], [1, 2]]” のように、「見つける対象」と「入れ替えた結果」というデータ構造を採用しています。 後者はこの「見つける対象」と「入れ替えた結果」というデータ構造を採用することで可能になっています (それが前者よりも効率がいいかはともかく)。

このように、バブルソートという簡単な例でも、その書き方は１つに限らないこと――ここで挙げた２つの他にもありますので考えてみてください――、そしてデータ構造とプログラム――あるいはアルゴリズム――は無関係ではないことを読み取っていただければと思います。