並び替えアルゴリズムを考える！（選択ソート編）
こんにちは「つけらっとゲームス」プログラム担当のとちです。
今回は並び替え（ソート）アルゴリズムについて考えてみましょう…え？
ちょっと前に同じような記事を見たって？
そうですね、ちょっと前にバブルソートについて解説しました。今回は選択ソートについてお話したいと思います。考え方的には単純でわかりやすい方法だと思うので、考え方だけでも覚えて行ってくださいね！
高校等で情報関連の勉強をしていて「学校で習ったけどよくわからん」という方や、これからプログラムを勉強しようという方にオススメです！
基本情報技術者［科目Ｂ］で出題されるアルゴリズムが苦手な方、不安な方も一緒に予習復習していきましょう！
これらの勉強に使えそうな関連記事は以下にまとめてます！（↓）
はじめに
この記事では、これまでのプログラミング学習関連記事と同様に以下の順番で解説していきます。
（１）処理手順を想像する（アルゴリズムを考える）
（２）処理手順を図形で表現する（フローチャートを考える）
（３）実際にコード化してみる！
コード化する際はExcel(VBA)を使用します。
VBAを使った経験が無くても、他の言語を使っている方でもシンプルな記述をするので、なんとなく内容は理解できると思います。
※Excelのソート機能ではなくVBAでコード化します。
今回の解説に使用するデータは以下の通りです。前回のバブルソートの記事に引き続き、回転寿司屋さんで使っている商品データの配列ですね。
商品番号 sNo と商品名 sName の添字は対応しています。これをsNoの昇順に並び替えします。下の表の様になるとソート成功です！
まぁ、これくらいのデータ量なら人間の手で並び替え可能ですが100件、200件になると大変です。プログラムに処理させましょう。
処理手順を想像する
まず、どんな処理をすればいいのか想像します。
前回のバブルソートの考え方はどうだったか復習すると…
配列の先頭から比較する。
sNoの0番目と1番目を比較し前者が大きい場合、0番目と1番目を交換。
sNoの1番目と2番目を比較し前者が大きい場合、1番目と2番目を交換。
これを配列の最後まで繰り返す、配列の最後尾はsNOの4番目。
sNoの4番目は最も大きい値になるので、これを確定させる。
配列の先頭から比較する。
sNoの0番目と1番目を比較し前者が大きい場合、0番目と1番目を交換。
sNoの1番目と2番目を比較し前者が大きい場合、1番目と2番目を交換。
これを配列の最後まで繰り返す、配列の最後尾はsNOの4番目だけど、4番目は確定しているので比較不要。sNoの3番目が最後尾となる。
sNoの3番目に、このループでの最も大きい値が入るのでこれを確定。
配列の先頭から比較する…と繰り返していき、すべて確定したら並び替えは完了している。
こんな感じでした。
隣り合った値を比較して交換していく、すると配列の端っこは確定する。これを繰り返すことで並び替えしているんですね。
選択ソート
では選択ソートの考え方はどうなっているのか、これを文章で表現するとこんな感じでしょうか？
sNoの0番目から4番目の中で最小値を探し、sNoの0番目と交換する。
sNoの0番目は、sNoの0～4番目の中で最小値として確定。
sNoの1番目から4番目の中で最小値を探し、sNoの1番目と交換する。
sNoの1番目は、sNoの1～4番目の中で最小値として確定。
これを繰り返して、すべて確定したら並び替えは完了している。
文章だと意味がわかりません。混乱するだけなので図で説明します。
前回同様、商品番号 sNo の昇順に並べるので 商品名 sName は一旦忘れますましょう。説明する為に sNo を横に並べますね。
選択ソートの考え方を図で表現すると以下のようになります。
内容はシンプル！
これなら思ったより考え方を理解できると思います。
ただ、ひとつだけ不安がでてきます。図中で「最小値を探し」という説明がされていますが、最小値ってどうやって求めるんでしたっけ？
正解は次の記事にあります。
一番「高い」「低い」「多い」「少ない」「大きい」「小さい」といったデータを見つける方法は、様々なシーンで出てくる考え方なので覚えておくと良いでしょう。
フローチャートを考える
それでは先程のアルゴリズムからフローチャートを考えます。今回も２つのパターンのフローチャートを用意しました。もちろん処理内容も配列の並び替え結果も同じです。
「あれ？ もう少し効率化できるんじゃね？」と思った方、そうですね。
でも、まずはこのフローチャートで進めていきます…
最小値Mnに999、つまりsNoではあり得ない大きな値を入れておきます。
Mn > sNo[ix] で判断している部分で最小値を探しています。
はじめて、ここの判断記号に到達した時のMnの中身は999ですから配列の中の値は必ず小さいハズですね。これを繰り返します。配列の中で最も小さい値を見つけ出します。
この値と、値を見つけた添字を変数に入れて覚えておきます。
配列をお尻の方まで探索したら、覚えておいた値とこれから確定する配列の頭の方の値と入れ替えます。
これで配列の先頭（左端）は最小値になっているので確定しましょう。
zmの値を１つ増やします。このzmの値が配列長Ln - 1 に達するとソート完了です。
実際にコード化してみる！
今回もExcel(VBA)を使ってプログラムコードを書きます。
まずは以下のようなユーザーフォームを作ります。ワークシートに問題のデータを入力しておきました。まだソートされていない状態ですね…
前回のバブルソートの説明でも使ったユーザーフォームなんですけどね。
先程のフローチャートを見ながらVBAでプログラムコード化します。
以下にプログラムコードを貼り付けます。Excel（VBA）を動かせる環境にある方はコピペすると使えますので試してみるといいでしょう。
Option Explicit
Dim sNo(0 To 4) As Single '【変数定義】商品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 Ln As Integer '【変数定義】配列の要素数（配列長）
Dim zm As Integer '【変数定義】確定済の添字（第1ループの添字）
Dim ix As Integer '【変数定義】探索用の添字（第2ループの添字）
Dim iM As Integer '【変数定義】最小値の添字
Dim Mn As Integer '【変数定義】最小値
Dim sNoSave As Integer '【変数定義】商品No 入替用変数
Dim sNameSave As String '【変数定義】商品名 入替用変数
'
Ln = 5 ' 配列長は5
'
For zm = 0 To Ln - 2 '■ 第1ループ 確定済の添字が 0 から Ln - 2 になるまで
'│
iM = -1 '├ 最小値の添字
Mn = 999 '├ 最小値（あり得ない値を代入）
'│
For ix = zm To Ln - 1 '├◆ 第2ループ 探索用の添え字が zm から Ln - 1 になるまで
'││
If Mn > sNo(ix) Then '│├▼ 最小値が商品No(ix)より大きい場合
Mn = sNo(ix) '││├ 最小値をこの商品Noにする
iM = ix '││└ 最小値の添字をこの時点のixにする
End If '││
'││
Next ix '│└ 第2ループ終端
'│
If iM > -1 Then '├◆ 最小値の添え字が初期値(-1)より大きい場合(何か変化があった場合)
sNoSave = sNo(zm) '│├ 商品Noの入替処理
sNo(zm) = sNo(iM) '│├ 〃
sNo(iM) = sNoSave '│├ 〃
sNameSave = sName(zm) '│├ 商品名の入替処理
sName(zm) = sName(iM) '│├ 〃
sName(iM) = sNameSave '│└ 〃
End If '│
'│
Next zm '└ 第1ループ終端
'
End Sub '「並び替え」ボタンをクリックした後に「配列の中身を表示」をクリックしてみましょう。すると以下のような画面が表示されました。正しくソートされているようですね。
少し効率化する
実際にVBAでプログラムコード化したところ、正しくソートされているのがわかりました。選択ソートの考え方も理解できていると思いますし、なので、この件は終わりでも全然OKです。が、
「もう少し効率化できそう…」と感じたら、試してみましょう。
余談ですが…
「誰が書いたかわからん、どうやって動いているかもわからん、超絶長くて複雑なプログラムコードの修正」というお仕事の場合は下手に触らない方がいいと判断をすることも…あるんですけど、まぁ今回は単純な例題です。
というわけで、フローチャートを少しだけ書き換えました。
赤文字が変わったところです。最初の１件を最小値として扱うようにしました。これにより入替判断の分岐条件も上記のように変更になりました。
ループ回数が減るので効率化にはなります。扱うデータ量が少ないので、あんまり効果を実感できませんがデータ量がある分だけ効率化されます。
プログラムもちょっとだけ変更すると効率化できます。
「並び替え改良型」ボタンを追加しました。
クリックすると以下のプロシージャが動きます。
'------------------------------------------------------------
' コマンドボタン3をクリックした時に動くプロシージャ
'------------------------------------------------------------
Private Sub CommandButton3_Click() ' 「並び替え改良型」ボタンをクリックした
'
Dim Ln As Integer '【変数定義】配列の要素数（配列長）
Dim zm As Integer '【変数定義】確定済の添字（第1ループの添字）
Dim ix As Integer '【変数定義】探索用の添字（第2ループの添字）
Dim iM As Integer '【変数定義】最小値の添字
Dim Mn As Integer '【変数定義】最小値
Dim sNoSave As Integer '【変数定義】商品No 入替用変数
Dim sNameSave As String '【変数定義】商品名 入替用変数
'
Ln = 5 ' 配列長は5
'
For zm = 0 To Ln - 2 '■ 第1ループ 確定済の添字が 0 から Ln - 2 になるまで
'│
iM = zm '├ 最小値の添字（探索範囲の先頭）
Mn = sNo(zm) '├ 最小値 （探索範囲の先頭）
'│
For ix = zm + 1 To Ln - 1 '├◆ 第2ループ 探索用の添え字が zm から Ln - 1 になるまで
'││
If Mn > sNo(ix) Then '│├▼ 最小値が商品No(ix)より大きい場合
Mn = sNo(ix) '││├ 最小値をこの商品Noにする
iM = ix '││└ 最小値の添字をこの時点のixにする
End If '││
'││
Next ix '│└ 第2ループ終端
'│
If iM > zm Then '├◆ 最小値の添え字が初期値(-1)より大きい場合(何か変化があった場合)
sNoSave = sNo(zm) '│├ 商品Noの入替処理
sNo(zm) = sNo(iM) '│├ 〃
sNo(iM) = sNoSave '│├ 〃
sNameSave = sName(zm) '│├ 商品名の入替処理
sName(zm) = sName(iM) '│├ 〃
sName(iM) = sNameSave '│└ 〃
End If '│
'│
Next zm '└ 第1ループ終端
'
End Sub '
当然ではありますがソート結果は同じになります。
おわりに
いかがでしたでしょうか？ 今回はランダムに並んでいるデータを昇順に並び替えるソートアルゴリズムのひとつ「選択ソート」を解説してみました。
考え方としてはバブルソートより単純かもしれません。
ここまで長い記事にお付き合いくださりありがとうございます！
もう少し、プログラミングの勉強したいなと思ってくれたら嬉しいです。
「VBAって結構ちゃんとしたプログラム作れるんだ～」と思った方はコチラがオススメです（↓）
もう少し見た目がかわいいゲームを作りたい方はコチラがオススメ（↓）
Unityで作りたい方はコチラをご覧ください（↓）
いいなと思ったら応援しよう！
