順位付けアルゴリズムを考えてみよう！
ゲームを作る他に専門学校のシステム系学科で外部講師もやってます。
今回は「順位付け」のアルゴリズムについて考えてみましょう！
情報関連の勉強をしていて「学校で習ったけどよくわからん」という方や、これからプログラムを勉強しようという方にオススメの内容です。
基本情報技術者［科目Ｂ］で出題されるアルゴリズムが苦手な方、不安な方も一緒に考えてみましょう！
情報科の勉強に使えそうな関連記事は以下にまとめてます！（↓）
はじめに
この記事では、これまでのプログラミング学習関連記事と同様に以下の順番で問題を解いていきます。
１．処理手順を想像する（アルゴリズムを考える）
２．処理手順を図形で表現する（フローチャートを考える）
３．実際にコード化してみる！
コード化する際はExcel(VBA)を使用します。
VBAを使った経験が無くても、他の言語を使っている方でもシンプルな記述をするので、なんとなく内容は理解できると思います。
（書いている人も普段はc#使っているので大丈夫、わかる、わかる！）
※ ExcelのRANK関数ではありません。
順位付けアルゴリズムをプログラムコード化した例です。
さて、今回のデータは以下の通りです。
紙飛行機を作って一斉に飛ばしたところ以下の飛距離となりました。さて飛行距離の順位はどうなるでしょう？
もちろん、遠くへ飛ばした人が１位です！
しかし意外と下の表を見ても、人間の目では瞬時にはわかりませんね。
処理手順をフローチャート化
どのように処理をすればいいのか想像してみましょう。
思いついたのは以下の考え方です。
とりあえず全員１位とする。
青山くん（0番目）を比較基準として、表の先頭から最後尾まで飛距離を比較します。比較基準の方が小さい場合は比較基準側の順位を+1します。
今田くん（1番目）を比較基準として、表の先頭から最後尾まで飛距離を比較します。比較基準の方が小さい場合は比較基準側の順位を+1します。
これを木村くん(6番目)まで繰り返します。
文章にすると逆に混乱するような気がします…
こんな時こそ図で表現。
小さくなってしまったので拡大して見てください…
では、これをフローチャート化します。
今回は２パターン（+1個）用意しました。
判断(分岐)記号で表現したフローチャートと、ループ記号で表現したフローチャートです。やってることは同じです。
（+1個）はサブルーチンです。
順位データを保持するwRank配列を「とりあえず全員１位にする」処理をします。この部分は同じなのでサブルーチンとして分けました。
パターン１のフローチャートではグルグル回っている処理が２つあります。パターン２のフローチャートを見るとわかりやすいのですが、ループが二重になっていますね。
外回りを第１ループ。中の小さく回っているのを第２ループとします。
第１ループで青山くん（0番目）の飛距離を比較基準とします。
第２ループに入って青山くん（0番目）の飛距離と比較します。
ここでは同じデータなので何もせず、第２ループを続けます。
第２ループで今田くん（1番目）の飛距離を比較します。
青山くん（0番目）の飛距離が小さいので順位+1をします。
これを木村くん（6番目）まで繰り返します。
第２ループが終わったら、第１ループに戻ります。
第１ループで今田くん（1番目）の飛距離を比較基準とします。
第２ループに入って青山君（0番目）の飛距離と比較します。
今田くん（1番目）の飛距離が大きいので何もせず第２ループを続けます。
これを木村くん（6番目）まで繰り返します。
第２ループが終わったら、第１ループに戻り…
これを木村くん（6番目）まで繰り返します。
すると、順位が確定するハズです。
なんとなく行けそうな予感がしませんか？
プログラムコード化してみましょう。
フローチャートをプログラムコード化
Excelで問題のデータとユーザーフォームを作成しました。
ユーザーフォームはLabel1～3に、それぞれ名前、飛距離、順位を表示します。「順位付け」CommandButton1をクリックすると順位が表示されます。
「順位付け」ボタンをクリックしてみました。
正しく順位付けされているでしょうか？
上手くいってるようですね。
プログラムコードは以下のようになっています。
Option Explicit
Dim wName(0 To 6) As String '【変数定義】名前配列
Dim wHiko(0 To 6) As Single '【変数定義】飛距離配列
Dim wRank(0 To 6) As Integer '【変数定義】順位配列
'------------------------------------------------------------
' フォーム初期化時に動くプロシージャ
'------------------------------------------------------------
Private Sub UserForm_Initialize()
Dim ix As Integer '【変数定義】配列にデータを入れるための添字
'
For ix = 0 To 6 '■ 初期データを代入しておくループ
wName(ix) = Sheet1.Cells(ix + 1, 1).Value '├ Sheet1の名前 を配列wNameに代入
wHiko(ix) = Sheet1.Cells(ix + 1, 2).Value '├ Sheet1の飛距離を配列wHikoに代入
Next ix '└ ループ終端
End Sub
'------------------------------------------------------------
' コマンドボタン1をクリックした時に動くプロシージャ
'------------------------------------------------------------
Private Sub CommandButton1_Click()
Dim ix As Integer '【変数定義】第1ループの添字
Dim ix2 As Integer '【変数定義】第2ループの添字
Dim wTName As String '【変数定義】文字列編集用 - 名前
Dim wTHiko As String '【変数定義】文字列編集用 - 飛距離
Dim wTRank As String '【変数定義】文字列編集用 - 順位
'
For ix = 0 To 6 '■ 第1ループ
wRank(ix) = 1 '├ 第1ループの対象データを暫定的に1位とする
For ix2 = 0 To 6 '├◆ 第2ループ
If wHiko(ix) < wHiko(ix2) Then '│├▼ 第1ループの対象飛距離と第2ループの対象飛距離を比較する
wRank(ix) = wRank(ix) + 1 '││└ 第1ループの対象飛距離が小さければ順位+1
End If '││
Next ix2 '│└ 第2ループ終端
Next ix '└ 第1ループ終端
'
For ix = 0 To 6 '■ 順位表示用ループ
wTName = wTName + wName(ix) + Chr(13) '├ 文字列編集 - 名前
wTHiko = wTHiko + Str(wHiko(ix)) + Chr(13) '├ 文字列編集 - 飛距離
wTRank = wTRank + Str(wRank(ix)) + "位" + Chr(13) '├ 文字列編集 - 順位
Next ix '└ ループ終端
'
Label1.Caption = wTName ' 画面表示 - 名前
Label2.Caption = wTHiko ' 画面表示 - 飛距離
Label3.Caption = wTRank ' 画面表示 - 順位
'
End SubこのコードをExcel(VBA)にコピペすると、皆さんの環境でも動きますので試してみるとより理解が深まりますよ！
いかがでしたでしょうか？ 今回は順位付けのアルゴリズムを……
ちょっと待って！？ もうちょっと効率化できそうじゃね？！
もうひとつの考え方
先程のやり方でも正しい順位付けになっていましたが、気になるところがありますよね。特にこの部分（↓）
第１ループで青山くん（0番目）の飛距離を比較基準とします。
第２ループに入って青山くん（0番目）の飛距離と比較します。
ここでは同じデータなので何もせず、第２ループを続けます。
同じ飛距離なのがわかっているデータ同士の比較は不要ですし、
青山くん（0番目）と今田くん（1番目）の比較についても、
今田くん（1番目）と青山くん（0番目）で再度比較しています。
これ、もうちょっと効率化できそうだよね？
ということで、考え方を効率化します。
とりあえず全員１位とする。
第１ループで青山くん（0番目）を比較基準とします。
第２ループで比較基準の次データを比較対象とします。つまり今田くん（1番目）が比較対象となります。比較して小さい方の順位を+1します。
これをデータ終端まで繰り返します。
第１ループで今田くん（1番目）を比較基準とします。
第２ループで比較基準の次のデータを比較対象とします。つまり上野くん（2番目）が比較対象となります。比較して小さい方の順位を+1します。
これをデータ終端まで繰り返します。
第１ループは加賀くん（5番目）まで繰り返します。
やっぱり、今回のアルゴリズムは文章にすると混乱しますね。
図で表すとこんな感じです。
小さくてゴメンナサイ！ 拡大して見てくださいね！
ではフローチャートで表現しましょう。
フローチャートの中身を確認しましょう。
第１ループで青山くん（0番目）の飛距離を比較基準とします。
第２ループに入って今田くん（1番目）の飛距離が比較対象です。
青山くん（0番目）の飛距離が小さいので、青山くんの順位を+1します。
第２ループを継続、上野くん（2番目）の飛距離が比較対象です。
上野くん（2番目）の飛距離が小さいので、上野くんの順位を+1します。
これを木村くん（6番目）まで繰り返します。
第１ループで今田くん（1番目）の飛距離を比較基準とします。
第２ループに入って上野くん（2番目）の飛距離が比較対象です。
上野くん(2番目)の飛距離が小さいので、上野くんの順位を+1します。
…見た感じ、そんなに変わってないような気がしますけど、ループ回数は大幅に減ってます。
第１ループで比較基準が変化すると、第２ループでは比較基準の次が比較対象になるからです。ここが大事。チェック対象がどんどん減ってますね！
これをプログラムコード化するとどうなるでしょう？
プログラムコードの改良
ユーザーフォームにボタンを１つ追加しました。
「(改良型)順位付け」CommandButton2 をクリックすると新しいプログラムコードで順位付けします。
プログラムコードは以下のようになりました。
コマンドボタン2をクリックした時のプロシージャを追加しました。
'------------------------------------------------------------
' コマンドボタン2をクリックした時に動くプロシージャ
'------------------------------------------------------------
Private Sub CommandButton2_Click()
Dim ix As Integer '【変数定義】第1ループの添字
Dim ix2 As Integer '【変数定義】第2ループの添字
Dim wTName As String '【変数定義】文字列編集用 - 名前
Dim wTHiko As String '【変数定義】文字列編集用 - 飛距離
Dim wTRank As String '【変数定義】文字列編集用 - 順位
For ix = 0 To 6 '■ 順位初期化ループ
wRank(ix) = 1 '├ 順位を全て1位とする
Next ix '└ ループ終端
'
For ix = 0 To 5 '■ 第1ループ
For ix2 = ix + 1 To 6 '├◆ 第2ループ
If wHiko(ix) < wHiko(ix2) Then '│├▼ 第1ループの対象飛距離と第2ループの対象飛距離を比較する
wRank(ix) = wRank(ix) + 1 '││└ 第1ループの対象飛距離が小さければ第1ループの対象者の順位+1
ElseIf wHiko(ix) > wHiko(ix2) Then '│├▼ 第1ループの対象飛距離と第2ループの対象飛距離を比較する
wRank(ix2) = wRank(ix2) + 1 '││└ 第2ループの対象飛距離が小さければ第2ループの対象者の順位+1
End If '││
Next ix2 '│└ 第2ループ終端
Next ix '└ 第1ループ終端
'
For ix = 0 To 6 '■ 順位表示用ループ
wTName = wTName + wName(ix) + Chr(13) '├ 文字列編集 - 名前
wTHiko = wTHiko + Str(wHiko(ix)) + Chr(13) '├ 文字列編集 - 飛距離
wTRank = wTRank + Str(wRank(ix)) + "位" + Chr(13) '├ 文字列編集 - 順位
Next ix '└ ループ終端
'
Label1.Caption = wTName ' 画面表示 - 名前
Label2.Caption = wTHiko ' 画面表示 - 飛距離
Label3.Caption = wTRank ' 画面表示 - 順位
End Sub
こちらも皆さんの環境にコピペすると動きます。
これが正しく動いたらCommandButton1のプロシージャはいらないですね。
どれだけ効率化したのか？
改良したことによって「効率化した！」と言われていますが本当だろうか？と疑問に思うのは大事なことです。最初のやり方と改良したやり方、どれくらい違うのか図にしますと…
比較した回数は半分以下になっています。これは驚き！
と、言いたいところですがif文がそれだけ複雑化しているので、データ量が少なければ扱いやすい方でいいかな…
ものすごく大量のデータを扱うなら改良型がいいでしょう。
おわりに
いかがでしたでしょうか？ 今回は複数あるデータを比較して順位を付けるアルゴリズムを考えてみました。
実際にExcel（VBA）でプログラムコード化して画面表示しましたが、ここまできたら順番通りに並び替えしたいですよね？
ええ、並び替えのアルゴリズムもあるんですよ。
というわけで、別の記事で並び替え（整列・ソート）のアルゴリズムについて考えてみましょう。
ここまで長い記事にお付き合いくださりありがとうございます！
また別の記事でお会いできるのを楽しみにしております！
いいなと思ったら応援しよう！
