
並び替えアルゴリズムを考える!(バブルソート編)
こんにちは「つけらっとゲームス」プログラム担当のとちです。
今回は並び替え(ソート)アルゴリズムについて考えてみましょう!
専門学校の非常勤講師として学生に教えていると、探索(サーチ)のアルゴリズムは早い段階で理解できているようです…が、並び替え(ソート)になると難易度が上がるのか苦戦している学生が出てきます。
そこで今回はソートアルゴリズムについて詳しく解説したいと思います。
高校等で情報関連の勉強をしていて「学校で習ったけどよくわからん」という方や、これからプログラムを勉強しようという方にオススメ!
基本情報技術者[科目B]で出題されるアルゴリズムが苦手な方、不安な方も一緒に予習復習していきましょう!
情報科の勉強に使えそうな関連記事は以下にまとめてます!(↓)
はじめに
この記事では、これまでのプログラミング学習関連記事と同様に以下の順番で問題を解いていきます。
(1)処理手順を想像する(アルゴリズムを考える)
(2)処理手順を図形で表現する(フローチャートを考える)
(3)実際にコード化してみる!
今回は更に(2)の時点でトレースしてみます。
資格試験などでは制限時間があって厳しいかもしれませんが、アルゴリズム・フローチャート・プログラムコードの間違いを探す方法としてトレースは有効な手段です。どうやってトレースするかも説明していきます。
コード化する際はExcel(VBA)を使用します。
VBAを使った経験が無くても、他の言語を使っている方でもシンプルな記述をするので、なんとなく内容は理解できると思います。
※Excelのソート機能ではなくVBAでコード化します。
さて、今回の問題に使用するデータは以下の通りです。
回転寿司屋さんで使っている商品データの配列だと思ってください。

商品番号 sNo と商品名 sName の添字は対応しています。
これを見ると商品番号 sNo の順番になっていません。気になるので並び替えしたいところです。

5件くらいのデータであれば人間の手で並び替えしてもいいんですが、回転寿司屋さんのネタって本当はたくさんありますよね。100種類のランダムな並び順だったら苦労します…ではプログラムにやってもらいましょう!
処理手順を想像する
まず、どんな処理をすればいいのか想像します。実は並び替えのアルゴリズムってたくさんあるんです。今回はバブルソートという方法で解決します。
バブルソートは隣の配列要素の値を比較して正しく並ぶように交換を繰り返していく方法です。
…いや、意味わからんわ!
意味がわからなくても大丈夫、詳しく説明しますよ~!
バブルソートは幾つかあるソートアルゴリズムの中でも基礎的な方法です。わたしも専門学校で並び替えを教える時は、まずバブルソートを教えます。
個人開発レベルのデータ量であれば、バブルソートをはじめとする基本的なソートアルゴリズムで十分だったりします。
バブルソート(交換法)
まず、商品番号 sNo の昇順に並べるので 商品名 sName は一旦忘れます。
説明する為に sNo を横に並べますね。

では早速バブルソートの考え方を説明します。


商品番号 sNo 配列の0番目と1番目、つまり sNo[0] と sNo[1] を比較します。sNo[0]の中身は数字の3、sNo[1]の中身は数字の1、前者が大きい。
昇順に並べるので配列の先頭が最も小さい数字であるべきです。なので、sNo[0] と sNo[1] の中身を交換します。
次に、sNo[1] と sNo[2] を比較します。sNo[1] の中身は数字の3になりました。sNo[2]の中身は数字の5です。前者が小さい場合は交換しません。
次に、sNo[2] と sNo[3]を比較します。sNo[2]の中身は数字の5、sNo[3]の中身は数字の4です。前者が大きいので交換します。
次に、sNo[3] と sNo[4]を比較します。sNo[3]の中身は数字の5になってます、sNo[4]の中身は数字の2です。前者が大きいので交換します。
いまの比較対象は配列の最後の要素です。この結果、配列の最後は最も大きな数字が入っていることになります。それがわかったら配列の最後はチェック不要。確定しました。
配列の最初に戻ります。
sNo[0] と sNo[1] を比較します。sNo[0] の中身は数字の1になってます。sNo[2]の中身は数字の3です。前者が小さい場合は交換しません…
これを繰り返します。但し、最後の方には確定している要素があります。そこはチェック不要です。
これを何度も繰り返すことによって配列全体が確定したら「ソート済み」となります。
ここまでの考え方は大きい数字を配列の後方に確定していく方法ですね。
もちろん逆でも可能です。
下の画像のとおり、小さい数字を配列の前方に確定してもOKですね。バブルソートは隣り合った配列の要素を比較して交換するのです。

上の画像の中にも書いてある通り、全ての配列要素が確定したらソート完了となります。
フローチャートを考える
それでは小さい数字を配列の前方に確定していく方法をフローチャートにしてみましょう。と言いたいところですが処理手順(アルゴリズム)を想像すると結構複雑です。苦戦する学生が出てくるのもわかりますね。
複雑な問題を解決する方法は「問題を切り分ける」です。
まずは配列要素の前後を比較して前者が大きい場合は交換する。小さい場合はそのままでよい。という部分だけをフローチャート化します。

比較するのは sNo の何番目か?
上のフローチャートでは0番目と、その隣の1番目でした。
交換する際はデータを上書きして喪失しないように、一旦別の変数に入れてから交換します。これを忘れるとソートできないので注意!!
何番目の部分、つまり添字を変数にすることで対応できそうです。更に配列の後方から比較して配列の先頭に最も小さい数字を確定するのであれば、添字の初期値は配列長から取得できそう。フローチャートを少し改良します。

上のフローチャートで配列最後と最後の手前を比較できました。
配列長は変数 LenS に入っているものとします。今回の問題のデータですと配列長は5です。
最後の方から先頭の方へ比較を進めて行きたいので、添字である変数 i を減らすループが必要になります。

これで配列の最後から先頭までループするフローチャートになりました。同時に配列先頭は商品番号の最小値が格納されています。ということは、更にこのフローチャートを繰り返す必要がありますね。
というわけで解答例です。今回も2パターン用意しました。判断(分岐)記号で表現したフローチャートと、ループ記号で表現したフローチャートです。やってることは同じです。
解答例(1)
判断(分岐)記号を使用した場合のフローチャートです。

フローチャート画像の右側にトレースした結果も残しておきました。
トレースについては後述しますので、そちらで詳しく説明します。
解答例(2)
ループ記号を使用した場合のフローチャートです。

トレースとは!?
「そもそもトレースって何?」から説明しましょう。
絵を描く時のトレース(トレス)だと描き写しするという意味になります。紙に下から光を当てて透けて見える絵を描き写すためのトレス台というものがありますよね。グラフィックツールだとレイヤー分けて描き写す方法もありますね。
場合によってはモノマネとかパクリというネガティブな意味があったりしますが、プログラミングにおけるトレースといえば、実は自然と誰しもやっていることだと思います。
問題を突き止めるため、または正しく動くか試すために各命令の実行を順番に確認する作業をトレースと言います。デバッグの手法の1つと言っていいでしょう。スクリプトエディタでステップ実行をするのもトレースですね。
アルゴリズムを考えたりフローチャートを書く時点でのトレース方法としては以下のやり方が良いでしょう。解答例(1)を再掲します。

配列 sNO の最上段は配列の初期状態です。これを正しい並び順にします。
配列が何段も書かれていますが、その下に変数が並んでいます。
変数 zm は整列済添字、つまり確定した要素数を意味します。
変数 i はループ内で使用している探索用添字です。
フローチャートの「開始」記号から順に1つ1つ線や矢印の順に処理していきます。変数内の数値が変化したら記録していきましょう。
例えば、開始から1つ進んで0を変数 zm に入れています。そしたら zmが0になったことを記録しておくんです。
引き続き1つ進むと LenS - 1 を 変数 i に入れています。i が4になりますね。
i が4になったことを記録しておきます。
これを「終了」まで順序良く記録していきましょう。考えたアルゴリズム、描いたフローチャートが正しければ正しく並び替えできるハズです。これで間違い気づけるので、学生さんだったら課題を提出する前に、一旦トレースすると良いでしょう(まじめにやるとかなり面倒臭いけどね…)
実際にコード化してみる!
今回も最後にExcel(VBA)を使ってプログラムコードを書きます。
まずは以下のようなユーザーフォームを作ります。ワークシートに問題のデータを入力しておきました。まだソートされていない状態ですね。

「並び替え」ボタンをクリックした後で「配列の中身を表示」ボタンをクリックすると正しい並び順になります。

並び替えは正しく動作しているようですね。
以下にプログラムコードを貼り付けます。Excel(VBA)を動かせる環境にある方はコピペすると使えますので試してみるといいでしょう。
Option Explicit
Dim sNo(0 To 4) As Integer '【変数定義】商品No配列
Dim sName(0 To 4) As String '【変数定義】商品名配列
'------------------------------------------------------------
' フォーム初期化時に動くプロシージャ
'------------------------------------------------------------
Private Sub UserForm_Initialize()
Dim i As Integer '【変数定義】配列にデータを入れるための添字
'
For i = 0 To 4 '■ 初期データを代入しておくループ
sNo(i) = Sheet1.Cells(i + 1, 1).Value '├ Sheet1の商品Noを配列sNoに代入
sName(i) = Sheet1.Cells(i + 1, 2).Value '├ Sheet1の商品名を配列sNameに代入
Next i '└ ループ終端
End Sub
'------------------------------------------------------------
' コマンドボタン1をクリックした時に動くプロシージャ
'------------------------------------------------------------
Private Sub CommandButton1_Click()
Dim tNo As String '【変数定義】文字列編集用 - 商品No
Dim tName As String '【変数定義】文字列編集用 - 商品名
Dim i As Integer '【変数定義】ループ添字)
tNo = "商品No" + Chr(13) '商品No 表題を代入
tName = "商品名" + Chr(13) '商品名 表題を代入
For i = 0 To 4 '■ 表示用ループ
tNo = tNo + Str(sNo(i)) + Chr(13) '├ 文字列編集 - 商品No
tName = tName + sName(i) + Chr(13) '├ 文字列編集 - 商品名
Next i '└ ループ終端
'
Label1.Caption = tNo ' 画面表示 - 商品No
Label2.Caption = tName ' 画面表示 - 商品名
End Sub
'------------------------------------------------------------
' コマンドボタン2をクリックした時に動くプロシージャ
'------------------------------------------------------------
Private Sub CommandButton2_Click()
Dim zm As Integer '【変数定義】整列済添字(第1ループの添字)
Dim i As Integer '【変数定義】探索用添字(第2ループの添字)
Dim sLen As Integer '【変数定義】配列長
Dim wNo As Integer '【変数定義】商品No 入替用変数
Dim wName As String '【変数定義】商品名 入替用変数
sLen = 5 '配列長は5
For zm = 0 To 4 '■ 第1ループ 整列済添字が4になるまで
For i = sLen - 1 To zm + 1 Step -1 '├◆ 第2ループ 配列の最後から整列済要素まで
If sNo(i - 1) > sNo(i) Then '│├▼ 隣り合った配列要素の大小比較
wNo = sNo(i) '││├ 入替処理
wName = sName(i) '││├ 〃
sNo(i) = sNo(i - 1) '││├ 〃
sName(i) = sName(i - 1) '││├ 〃
sNo(i - 1) = wNo '││├ 〃
sName(i - 1) = wName '││└ 〃
End If '││
Next i '│└ 第2ループ終端
Next zm '└ 第1ループ終端
End Subプログラムコードの右側にはコメント化している各行の説明があるので参考にしてくださいね。
おわりに
いかがでしたでしょうか? 今回はランダムに並んでいるデータを昇順に並び替えるソートアルゴリズムのひとつ「バブルソート」を解説してみました。ソートアルゴリズムの基礎といえる方法です。覚えておきましょう。
ここまで長い記事にお付き合いくださりありがとうございます!
もう少し、プログラミングの勉強したいなと思ってくれたら嬉しいです。
「VBAって結構ちゃんとしたプログラム作れるんだ~」と思った方はコチラがオススメです(↓)
もう少し見た目がかわいいゲームを作りたい方はコチラがオススメ(↓)
Unityで作りたい方はコチラをご覧ください(↓)