アルゴリズム？プログラミング。 - バブルソート

バブルソートは最も単純なソート、並び替え方法としていろんなところで紹介されています。

仕組みは隣の値(数字)と比べてもし順番に並んでいなければ入れ替えるというものです。たくさんの値があれば順番に比較、入れ替えを行って最終的に並び替えができるというものです。Colabで試しながらやっていきます。

基本は

a = 5
b = 3

print(a,b)

if a > b:
    a,b = b,a

print(a,b)

こんな感じで2つの値を考えるということです。この例はPythonの簡単な方法で入れ替えています。

値の入れ替えについては

数字がたくさん入ったリストの並び替えをします。この比較、入れ替えはリストなのでfor inループを使って連続して処理すれば良いです。その仕組みを考えてみます。

リストの数字を調べていくのですが、方法としてリストのインデックスでいうと[0],[1]を比較していく方法をとります。

 for j in range(1,len(num)):
　　if num[j] < num[j-1]:

範囲指定ができるrange()関数でスタートは"1"から始めてリストの長さ分の回数を繰り返してやります。

range(1,len(num))

並び替えはというと、条件分岐で

　if num[j] < num[j-1]:

num[j-1]　num[j]とを比較。

"1"から始めているので比較対象のインデックスは

1-1 = "0"　と　"1"

として実際の比較としては、

num[1] < num[0]

となります。これで2つの値を比較することができます。

では2つの数字を比較して前の数字が大きければ、前後の順番を入れ替えるという処理をfor inループで実行してみます。

num = [8,4,1,5]
 
for j in range(1,len(num)):
     if num[j] < num[j-1]:
         num[j], num[j-1] = num[j-1], num[j]

print(num)

実行結果は

[4, 1, 5, 8]

一番おおきな数字が一番右端に移動しています。一番大きな数字は順番通り、整列できたということです。

これをリストの値の数だけ繰り返してやれば全ての数を整列できそうです。

   for i in range(0,len(num)):

リストの値の数だけループする処理を追加します。

for i in range(0,len(num)):
    for j in range(1,len(num)):

に2重でfor inループを作ってやるとリストの値の数だけ比較して入れ替える操作を実行できるようになっているはずです。

全コードは以下となります。

num = [8,4,1,5]
 
for i in range(0,len(num)):
    for j in range(1,len(num)):
        if num[j] < num[j-1]:
            num[j], num[j-1] = num[j-1], num[j]

print(num)

実行すると全ての値が並び替えされました。

並び替えはうまくいきますが、ここでちょっと工夫をしてみます。1回ループが終わると、比較する数字も減らして行っても大丈夫なはずなので、

for i in range(0,len(num)):
    for j in range(1,len(num) - i):

としてやれば効率も上がります。