バブルソートをPythonで書いてみた。

バブルソートについての2つ目の記事です。前回の記事でバブルソートとは？と取り上げて、ソート方法の考え方やアルゴリズムの解説を書きました。今回は実際に、Pythonでバブルソートを書いていきます。

バブルソートのおさらいを少しだけ

バブルソートはソート（並べ替え）方法の１つで、下図のようなバラバラのものを小さいもの順（昇順）または大きいもの順（降順）に並べ替えるものでした。

この際にバブルソートはバラバラのもの（上図青枠内）の一番後ろ（または一番前）から隣り合う数字同士の大小を比較して、昇順（または降順）になるように入れ替えてという操作を繰り返して、並べ替えるという方法でした。

あわせて読みたい

バブルソートとは？【アルゴリズム解説】 ソート（sort）とは、日本語で「並べ替える、分類する、仕分けする」などの意味があります。プログラミングでソートというと、バラバラに並んだ数字のカードを小さいも…

Pythonで書いてみた。

文字だけではイメージしにくいと思いますので、実例を紹介していきます。また、その操作をPythonコードに落とし込みます。手順としては、一番後ろ（または一番前）のカードから順に大小を比較します。今回の例では、昇順（小さいものから大きいものへ）で並べ替えていきたいと思います。

Step1：一番後ろのカードから

まず始めに、一番後ろのカードから順に隣り合うカードの大小を比較して、右側のカードの方が小さい場合はカードを入れ替えるという操作を行います。

Step1-1：3と1のカードの比較

まずStep1-1として3と1のカードを比較します。一番後ろのカード（3）とその左横のカード（1）を比較して、一番後ろの数字の方が大きければ、そのまま。小さければカードを入れ替えます。今回は一番後ろである3のカードの方が1より大きいのでそのままです。

ここの部分をコードで書くと以下のようになります。Step0の説明を全くしてこなかったのですが、初めに上記カードをリストCardsに格納しています。

#Step0
Cards = [4,2,5,1,3]
#Step1-1
if Cards[3] > Cards[4]:
    card = Cards[4]
    Cards[4] = Cards[3]
    Cards[3] = card

※Pythonのリストは0から開始する事に注意です。

ここでは一番後ろ（Cards[4]）のカードとその左隣（Cards[3]）のカードを比較しています。もしCards[3]の方が大きければCards[4]とCards[3]を入れ替えるようにしています。ただ、人の手で入れ替えるように同時に入れ替えることは難しいので、入れ替える前のCards[4]を変数cardに代入して、上書きを回避させます（6行目）。その上で、入れ替えが発生する場合はCards[3]をCards[4]に代入します（7行目）。そして、最後に変数cardに代入していた値をCards[3]に代入して完了です（8行目）。

Step1-2：1と5のカードの比較

続いて、Step1-2として、1と5のカードを比較します。右側のカード1と左側のカード5を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が5より小さいので、入れ替えます。

この部分をコードにすると以下のようになります。基本的にStep1-1で行ったことと同じで、Card[#]の中身の数字が1つずつ小さくなっただけになります。

#Step0
Cards = [4,2,5,1,3]
#Step1-1
if Cards[3] > Cards[4]:
    card = Cards[4]
    Cards[4] = Cards[3]
    Cards[3] = card
#Step1-2
if Cards[2] > Cards[3]:
    card = Cards[3]
    Cards[3] = Cards[2]
    Cards[2] = card

ここまでのStepを実行するとリストCardsの中は以下のように変更になっています。

[4, 2, 1, 5, 3]

Step1-3：1と2のカードの比較

続いて、Step1-3として、1と2のカードを比較します。右側のカード1と左側のカード2を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が2より小さいので、入れ替えます。

この部分をコードにすると以下のようになります。基本的にStep1-2で行ったことと同じで、Card[#]の中身の数字が1つずつ小さくなっただけになります。

#Step1-3
if Cards[1] > Cards[2]:
    card = Cards[2]
    Cards[2] = Cards[1]
    Cards[1] = card

Step1-4：1と4のカードの比較

続いて、Step1-4として、1と4のカードを比較します。右側のカード1と左側のカード4を比較して、右側のカードの方が大きければ、そのまま。小さければカードを入れ替えます。今回は右側のカードである1のカードの方が4より小さいので、入れ替えます。

この部分をコードにすると以下のようになります。基本的にStep1-3で行ったことと同じで、Card[#]の中身の数字が1つずつ小さくなっただけになります。

#Steo0~Step1-3省略
#Step1-4
if Cards[0] > Cards[1]:
    card = Cards[1]
    Cards[1] = Cards[0]
    Cards[0] = card

ここまでの操作（Step1）で一番左端（1のカード）が確定しました。

Step1のコードをまとめる

Step1のコードを1つ1つ書いているととても長く、5個の数字の並べ替えですらStep1だけで17行のコードになってしまいました。100個や1000個の数字の並べ替えの時はとても対応できないので、ここまでのコードをFor文の繰り返し処理でまとめます。

あわせて読みたい

【Python】for文(ループ)の作り方と使い方 1～10までの値を足し算したい時、1 + 2 + 3 + …としているととても時間がかかります。1～10までならまだ手で打って対応できますが、1～1000までとなるととても対応でき…

Step0はそのままにします。
Step1-1を見直すと、リストの要素の数5から1引いたものがリストの最後尾5-1＝4になり、その左隣5-2＝3の要素と比較やそれぞれを代入しています。

#Step1-1
if Cards[3] > Cards[4]:
    card = Cards[4]
    Cards[4] = Cards[3]
    Cards[3] = card

また、Step1-2も更に1ずつ引いたものの比較や代入しています。この辺りに法則性があり、For文で繰り返し処理ができそうです。
リストの要素の数をnとすると一番後ろの要素はn-1、その左隣はn-2なので、For文で書くと以下のようになります。

▼関連記事：range関数の使い方

Cards = [4,2,5,1,3]
n = len(Cards)
for i in range(n-1,0,-1):
    if Cards[i-1] > Cards[i]:
        card = Cards[i]
        Cards[i] = Cards[i-1]
        Cards[i-1] = card

Step2以降のコードもまとめて

Step2で再び一番後ろから数字の比較を行っていきます。ただ、一番前のカードまで比較を行うとStep1と同じになってしまいます。

そこで、Step1で一番前のカードが確定という情報を使って、一番前と一番前の右横のカードの比較を省略します。また、Step2で一番前から2番目のカードが確定します。

続いて、Step3でも一番後ろのカードから順々に比較を行っていきますが、Step1で一番前のカードが確定、Step2で一番前から2番目のカードが確定という情報を使って、一番前から2番目のカードの比較を省略します。また、Step3で一番前から3番目のカードが確定します。詳しくは前回の記事を参照ください。

この部分を見ていくと、Step1で一番前（1番目）のカードが確定、Step2で一番前から2番目のカードが確定（1番目のカードの比較は省略）、Step3で一番前から3番目のカードが確定（2番目のカードの比較は省略）となっていて、数字の法則性がありそうです。

上記の
for i in range(n-1,0,-1):
の0の部分が一番後ろ（要素：n-1）から、どのカードまで比較を行うか、に該当するので、この部分を変数にすればfor文で対応できそうです。
Step1：0
Step2：1
Step3：2
なので、0から始めてStepが1つ増えるごとに1ずつ増えて、ｎ-2まで比較を行えばできそうです。for文で対応すると
for j in range(n-1):
でできて、これが更に上記の
for i in range(n-1,0,-1):
にかかってくるので、for文の入れ子（ネスト）で対応できそうです。
実際のコードは最後の出力にprint()関数もつけると

Cards = [4,2,5,1,3]
n = len(Cards)
for j in range(n-1):
    for i in range(n-1,j,-1):
        if Cards[i-1] > Cards[i]:
            card = Cards[i]
            Cards[i] = Cards[i-1]
            Cards[i-1] = card
print(Cards)

'''
【実行結果】
[1, 2, 3, 4, 5]

これでコードを完成することができました。jの部分を0のままでも同じ結果を得る事はできるのですが、確定している箇所も再度確認が入り、不要な処理（不要な時間）が発生するのでjにして、最小限の計算処理にするようにしています。

降順にする場合

降順にする場合はとても簡単で
if Cards[i-1] > Cards[i]:
を
if Cards[i-1] < Cards[i]:
>を<にするだけでできます。以下のコードのようになります。

Cards = [4,2,5,1,3]
n = len(Cards)
for j in range(n-1):
    for i in range(n-1,j,-1):
        if Cards[i-1] < Cards[i]:
            card = Cards[i]
            Cards[i] = Cards[i-1]
            Cards[i-1] = card
print(Cards)

'''
【実行結果】
[5, 4, 3, 2, 1]

前から順番に比較していく場合（昇順）

前から順番に左右のカードを比較する事もできます。Step1だけのコードは以下のようになります。

Cards = [4,2,5,1,3]
n = len(Cards)
for i in range(n-1):
        if Cards[i] > Cards[i+1]:
            card = Cards[i+1]
            Cards[i+1] = Cards[i]
            Cards[i] = card

pythonのリストは0から始まるので、iはn-1番目までにします。そして、左隣の大きければ左右を入れ替えるという操作にします。これだけだとStep1の処理しかできないので、for文の入れ子にして、全Stepが対応できるようにします。

Cards = [4,2,5,1,3]
n = len(Cards)
for j in range(n-1,0,-1):
    for i in range(j):
        if Cards[i] > Cards[i+1]:
            card = Cards[i+1]
            Cards[i+1] = Cards[i]
            Cards[i] = card
print(Cards)

Step1で一番後ろ（要素：n-1）が確定、Step2で一番後ろから2番目（要素:n-2）が確定…と続くので、変数jはn-1から始まり、要素0（一番前）までfor文が一回回るごとに1ずつ減るようにしています。

前から順番に比較していく場合（降順）

降順にする場合も先程の例と同じで書き換えるのは簡単です。
if Cards[i] > Cards[i+1]:
を
if Cards[i] < Cards[i+1]:
のように>を<に変えるだけで完了です。

Cards = [4,2,5,1,3]
n = len(Cards)
for j in range(n-1,0,-1):
    for i in range(j):
        if Cards[i] < Cards[i+1]:
            card = Cards[i+1]
            Cards[i+1] = Cards[i]
            Cards[i] = card
print(Cards)

＊
＊
＊
コードだけ見て分かりにくい時は、デバッカーを使ったり、紙に数字を入れて実際にコードを書きだしてみると、理解が進むのでオススメの方法です。