【知識理解】「バブルソート」の図解でアルゴリズムに触れよう

はじめに

プログラムの基本は、「変数の取り回し」、「条件分岐」、「繰り返し」でできています。
しかし、「本当にこんな単純なことで、複雑なプログラムができるのか？」、疑問に思うかもしれません。

そんな時に手助けになるのが「アルゴリズム」です。

Anacondaのメリット／デメリットとPython環境構築

Pythonでプログラミングの勉強をしたいけど、なにから始めていいか分からない。プログラミングの勉強を始めるなら、自分のPCでプログラムを書いて実行できるように「環境構築」から始めると良いよ。「環境構築」って、P...

uniuni-diary.com

2021.09.21

アルゴリズムとは

アルゴリズムとは、「何らかの問題を解くとき、それを単純な処理の組み合わせで手順化したもの」です。
ここで言う、「何らかの問題」とは計算問題など学術的なモノに限らず、じゃんけんをやらせたい、画面に図形を表示させたいなど「コンピュータにやらせたい事」くらいに捉えてください。

すなわち、コンピュータにやらせたいことを「変数の取り回し」、「条件分岐」、「繰り返し」の基本処理の組み合わせの手順にしてしまいます。

また、アルゴリズムは「問題」の数だけでなく、通常は「１つの問題」に対して複数のアルゴリズムが存在します。

このように、問題が解けることも重要ですが、工夫によって効率的に処理できる手順にすることも同じくらい大切になります。

もちろん、私達が解きたい問題のほとんどには、既に素晴らしいアルゴリズムがあります。
※人類で始めて直面する問題を解きたい人がいたら、話は別ですが（笑）

なので、私達は既にあるアルゴリズムを組み合わせて、プログラムを作ることに集中できます！！

並び替えアルゴリズム「バブルソート」の図解

みなさん、ランダムに並べた5個の数字を昇順に並び替える手順を作ってください！！
・・・と、急に言われても困りますよね、、、

そもそも、「並び替えってどうやってるか？」を真剣に考えると結構難しいですね。
※もちろんプログラムを作るときは、「良い感じに〜」は禁止です！！

ここで、最も単純な並び替えアルゴリズムである「バブルソート」を紹介します。
バブルソートの基本概念は、「隣り合う数字を比較して、必要なら入れ替えるを繰り返す」です。

5個の数字を昇順に並び替える例で見ていきます。

まず、後ろから順に２つの数字を比較して「左側の数字が大きければ入れ替え」、「右側の数字が大きければそのまま」にする処理を先頭まで繰り返します。
これによって、先頭が最も小さい数字になりました。

次に、同じ処理を後ろから順に先頭の１つ手前まで繰り返し行います。
※先頭は既に最小の数字が置かれているので、比較する意味はありません。
これによって、先頭から２つ目まで昇順に並びました。

さらに、同じ処理を後ろから順に先頭の２つ手前まで繰り返し行います。
（そろそろ、分かっちゃいましたよね・・・）

最後は、同じ処理を後ろから順に先頭の３つ手前まで繰り返し行います。

比較と入れ替えを繰り返しただけで、見事にバラバラの数字を昇順に並べ替えることができました。

余談ですが、「バブルソート」の名前は、（昇順ならば）小さい数字が泡のように左側に寄っていく（浮かんでくる）様子に由来しています。

「バブルソートプログラム」の全体像

#######################
#  並び替える配列を設定   #
#######################
sList = [10, 4, 6, 15, 9, 14, 2, 5, 0, 13, 11]
print(sList)

################
#  バブルソート  #
################
for i in range(len(sList)):

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

        # 隣り合う要素の大小を比較
        # （後の要素の方が小さければ入れ替え）
        if sList[j] < sList[j-1]:
            
            # 要素の入れ替え
            tmp          = sList[j]
            sList[j]    = sList[j-1]
            sList[j-1] = tmp

#######################
#  並び替える結果の確認   #
#######################
print(sList)

プログラム作成時の注意点

図解したバブルソートをプログラムに起こすとき、慣れていないと「forループの書き方」と「配列のインデックス」がピンとこないと思います。
その場合、めんどくさがらずに i、j に具体的な数字を入れながらプログラムが実行されていることを紙に書きながら理解しましょう！
※数字5個の並び替え程度なら30分もかからないでしょう

慣れれば、頭の中で考えられるようになりますが、最初から泥臭いですが愚直にトレーニングを重ねるのが上達への近道です。

また、数字を入れ替えるときは別の変数（tmp）を利用しています。

tmp        = sList[j]
sList[j]   = sList[j-1]
sList[j-1] = tmp

ただし、Pythonでは別変数を省略して、以下のように記述することもできます。
ムダな変数を作らない観点ではこちらの方が良いプログラムですが、まずは基本を抑えるためにも紹介だけにしておきます。

sList[j], sList[j-1] = sList[j-1], sList[j]

最後に

プログラムは、一見すると複雑な処理を行なっているよう見えます。
しかし、よくよく見るとそれは単純な処理の組み合わせでできているのです。

複雑なモノを単純化するのは、場数や慣れが必要ですが、１歩ずつ一緒に学んでいきましょう！