こちらの記事は次のような方のニーズに応えるために書いています。
- 基本情報技術者試験を受けようと思うけど、アルゴリズムがわからない！
- Excelマクロでアルゴリズムの勉強をしてみたい。
- どうしてリンゴの画像なの？
アルゴリズムは基本情報技術者試験では必須の知識ですが、考え方を理解するのは難しいです。私が基本情報技術者試験の受験対策として実施したアルゴリズムの学習方法をご紹介します。
まず、アルゴリズムって何？という方は下記のリンクでご説明していますので、見てみていただけるとありがたいです。
私の基本情報技術者試験の合格体験記はこちらで公開しています。
アルゴリズムは並べ替え（ソート）で学習しよう
私がオススメする、アルゴリズムを理解する方法は並べ替え（ソート）です。
基本情報技術者試験のシラバスの「大分類1：基礎理論中分類2：アルゴリズムとプログラミング」において、代表的なアルゴリズムとして以下の並べ替えを記載しています。
- 選択ソート：数列内の最小値を探索し、左端から入れていく方法
- バブルソート：右または左から隣の数字と交換して整列させる方法
- マージソート：ソートする数列を半分に分割していき、最小単位まで分割したあとで、それを比較しながらもとに戻していく方法
- 挿入ソート：最初に左端をソート済に設定し、比較交換していく方法
- シェルソート：一定間隔毎に要素を取り出して挿入ソートを実行して間隔を縮ていく方法
- クイックソート：ピボットという基準値をランダムに選択し、先頭からピボットよりも大きいか小さいかの分割を繰り返す方法
- ヒープソート：ヒープ（二分木）という構造を利用して、根の数字を取り出していき、再構築するのを繰り返す方法
これらの並べ替えは、午前試験でも理論として聞かれることも多いですね。
この並べ替えは、どの方法を採用するかにもよりますが、アルゴリズムとしては比較的理解しやすい方だと思います。
単純な例を用いて、並べ替えがどのような手順でおこなわれるかをよく理解することが、アルゴリズムの理解向上の鍵です。
リンゴのカードでバブルソートの確認
私が最初に取り組んだのは、とある参考書に書いてあった、リンゴのカードの並べ替えです。ここではバブルソートについて例としてやってみます。
手順の確認
- リンゴの絵に１～５までの数字が書いてあるカードを準備します。
- カードをランダムに並べます。
- バブルソートのルールにしたがって、並べ替えをおこないます。
1) 右端から順に、隣同士のカードを比較して、左側が大きければ交換、左側が小さければそのまま。
2) 左端まで到達したら、左端のカードは確定。
3) 1)と2)を繰り返してすべてのカードが確定するまで続ける。
これだけです。
ですが、慣れないうちはこれだけでも本当に難しい。
カードを使った並べ替えの実践
カードを並べ替えていくだけなら簡単では？と思われるかもしれません。
しかも、この例だと⑦より後はやる意味がない！と思われたでしょうか。
ですが、これをコンピュータにやらせる場合どうするでしょうか？？
コンピュータは並べ替え終わった状態がわからないので、どこまで処理が終わったら終了、ということを教えてあげなければいけません。
そうした、すべての手順、条件を頭で考えるのが、アルゴリズムの理解には必要です。
コンピュータに伝えることの確認
この並べ替えの内容をコンピュータに伝えるにはどのような要素が必要か？
カードを目の前にして考えます。
- カードの枚数
- 右から並べ替えをしていくこと
- 隣同士のカードを比較すること。左側が小さければ交換、大きければそのまま。
- 左端まで到達したら右端に戻ってやり直す
- すべてが確定したら終了
ルールを考えれば、これくらいの条件が思い浮かぶと思います。
ただ、これだけでもちょっと足りません。もう少しコンピュータに理解できるように考える必要があります。
例えば、カードの枚数は５枚ですが、５枚のカードを箱に入れるイメージで、左端を１番目の箱、右端を５番目の箱に入れる、と考えるとコンピュータにも伝わります。
この「番目の箱」と実際のカードの数字を頭の中で入れ替えていきます。
順番にやっていくので、「カード全部の枚数ー１」が１巡目の比較回数、２巡目ならば「カード全部の枚数ー２」が比較回数、と繰り返せばよさそうです。
では、入れ替えはどうするか？ここでは【１巡目】②の３番目と４番目の入れ替えのケースを考えます。
- ３番目の数字を４番目に入れる
- ４番目の数字を３番目に入れる
こうすれば交換できそうです。ただ、３番目の数字を４番目に入れた時点で、３番目と４番目の数字が同じになってしまいます。
そこで、以下のように「仮の箱」を用意して、交換をおこないます。
こういった形で、コンピュータが扱えるような状態にして、並べ替えをしていくことができます。
リンゴのカードである必要はありませんが、初めてこうしたアルゴリズムに触れるのであれば、実際に手で触ってやってみるのは記憶に残っていいと私は考えます。
私が過去使用したカードを再現したものを作成しましたので、よろしければダウンロードしてプリントアウトし、切り取ってお使いください。
Excelマクロでバブルソートの実装
ここまで、実際にカードを使って見てみましたが、今度はExcelマクロでやってみましょう。最初からExcelマクロを作成するのは難しいでしょうから、下記のコードを使用して、数字の動きを見てみてください。
並べ替え用の数字を２行目に入力（１００個まで対応しています）
Excelマクロ用のVBAコードは以下のとおりです。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | Option Explicit Sub BubbleSort() '前の結果消去 Rows("4:103").ClearContents Rows("4:103").Interior.Color = vbWhite 'ソート対象のカード枚数を取得 Dim mai As Long mai = Cells(2, 1).End(xlToRight).Column '箱の準備 Dim hako(100) As Long 'カードの番号を箱に入れていく Dim i As Long For i = 1 To mai hako(i) = Cells(2, i) Next i '右端から左へ行く回数を定義（カード枚数-1） Dim j As Long j = mai - 1 '途中データ表示用のカウント Dim count As Long count = 4 '入れ替えのための仮の箱を作る Dim kari As Long '隣り合う数字を比較して並び替え Dim k As Long, l As Long For k = 1 To mai - 1 '右端から左側へ進んでいくためのstep -1 For i = j To 1 Step -1 '左側の箱が小さい場合に入れ替え If hako(i + 1) < hako(i) Then '仮の箱を使って箱の数字を入れ替える kari = hako(i) hako(i) = hako(i + 1) hako(i + 1) = kari End If Next i '途中経過の表示 For l = 1 To mai Cells(count, l) = hako(l) Next l count = count + 1 Next k '最終結果の書式変更 Rows(count - 1).Interior.Color = vbYellow End Sub |
これを実行しますと、このような結果が出てきます。
左端に行くたびに経過が出るようにしています。
最終結果は黄色のセルで表示しています。
カードで確認していたときもそうでしたが、このExcelマクロの中でも隣同士の比較、仮の箱を使用した入れ替えがキーポイントになります。
この部分をスムーズに理解できるようになると、アルゴリズムについての考えがすすんだと考えていいと思います。
ぱっと見たところでは、すごい処理をされているようなプログラムでも、中身を見てみると、こんな感じで地道に比較、足し算、入れ替えを繰り返しているんですね。
こうした地道な考え方を理解してじっくりと取り組めばアルゴリズムも怖くないです！
今回のExcelマクロはZIP形式で下記リンクからダウンロード可能ですので、よろしければお試しください。
以上、ここまでお読みいただきましてありがとうございました。
