アルゴリズム2
こんにちはkazutoです。今回は、アルゴリズムシリーズの第２弾です。基本的なソートアルゴリズムを3つを実際にソースコードに置き換えていきます。
ソートとは
ソートとは、データの集合を一定の規則に従って並べることです。日本語では、整列、並べ替え、という意味を持ちます。
具体的な例を挙げると
- 社員IDの主キーを基準に降順に並べる
- 配列の中に格納された数字を昇順に並べ替える
- ○年✖︎✖︎組の通信簿を名前順に並び替える
とかです。
要するにデータの並び順に規則性を持たせて、綺麗に並び替えるという事ですね。
バブルソート
バブルソートとは、隣り合うふたつの要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。
隣の要素の値を
- 大きいか？
- 小さいか？
と条件によって並び替えていきます。文字だけの解説では理解できないと思うので、下記の動画を参照してください。
フローチャートを確認しよう
バブルソートの特徴を抑えた所で、バブルソートをフローチャートで表現をしていきましょう。
バブルソートは、フローチャートで表すと上記の様になります。実装の肝は、値を入れ替える点ですね。一時的に用意した変数tmpを使って入れ替るという点に着目して実装していきましょう。上記のフローチャートを参考に次のトピックで、実際にソースコードに置き換えてみましょう。
コードに置き換えよう
フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう
| 変数 | 概要 |
|---|---|
| array | 配列 |
| i | 配列の添字&ループ回数 |
| j | 配列の添字&ループ回数 |
| temp | 仮置き箱 |
def bubble_sort(array)
i = 0
while i < array.length-1
j = 0
while j < array.length-1
if array[j] > array[j+1]
temp = array[j]
array[j] = array[j+1]
array[j+1] =temp
end
j+=1
end
i+=1
end
array
end
array =[2,3,45,5,1,3,5,21,12,23]
bubble_sort(array)
puts array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]それでは、解説していきます。
i = 0まずは、変数iを初期化して、ループ処理を行う準備をします。
while i < array.length-1
j = 0
endその後、while文を用いて、外側のループ処理を定義をします。なお、指定した条件は、iが配列arrayの要素の数より小さい限り繰り返すという内容になります。また、このタイミングで、内側のループ処理に必要な変数j を定義をしておきます。
while j < array.length-1
end次に内側のループ処理を定義をしていきます。まあ、指定する条件は、外側のループ処理と変わりません。jが配列arrayの要素の数より小さい限り繰り返すという内容になります。上記の様に、繰り返しが2重になっている構造を2重ループと言います。なお「 フローチャートを確認しよう」で作成した通り、2重ループの関係性は
- i
→配列操作を行う回数を指定するループ処理 - j
→実際に配列操作を行うループ処理
となります。
if array[j] > array[j+1]
temp = array[j]
array[j] = array[j+1]
array[j+1] =temp
endバブルソートは、隣り合うふたつの要素の値を比較して条件に応じた交換を行うという特徴があります。今回は、配列内を左から右に探索していき、配列の最後が一番大きい数になる様に実装しますので、最終的に
最後から2番目の数 < 最後の数という関係性になります。つまり、最後の数が一番大きい数になるという事です。要するに、最後の数が一番大きい数になる様に矛盾を無くせば良いだけですので、array[j] > array[j+1]という様に、左辺の数が右辺の数より大きかった場合にお互いの数を入れ替えると条件を提示をすれば、矛盾が無くなり、処理が成立します。
temp = array[j]
array[j] = array[j+1]
array[j+1] =temp具体的な処理内容は、上記の通りです。ポイントは、tempという「仮置き箱」に一時期的に左辺の数を格納している点です。この作業を怠ると上手く値を交換する事ができません。理由は、逐次実行というプログラミングの特徴によるものです。通常、ソースコードは、上から順に読み込まれていきます。もし、「仮置き箱」を用意をせずに値を交換した場合、変数が上書きされどちらも同じ値になってしまいます。
この様な理由から、tempという「仮置き箱」を用意をし、値を交換をしています。ちなみに下記の様に分割代入を用いれば、ワンライナーで記述する事ができます。
array[j],array[j+1] = array[j+1], array[j]こちらのソースコードでも、問題無くプログラムは動きますが、一見、何をしているのか、わかりづらいので、前者で実装をしました。
j+=1
end変数jに+1をしています。この記述を忘れると無限ループに陥るので忘れずに記述をしてください。
i+=1
endこちらも同様、変数iに+１をしています。この記述を忘れると無限ループに陥るので忘れずに記述をしてください。
以上でバブルソートの解説を終了します。バブルソートは、個人的には、整列アルゴリズムの中で一番わかりやすい構造だと思います。まずは、バブルソートをマスターしましょう！！
選択ソート
選択ソートとは、配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替える整列アルゴリズムです。要するにソート されていない配列の要素の、
- 最大値
- 最小値
を見つけて並び替えるという事ですね。文字だけの解説では、理解できないと思うので、下記の動画を参照してください。
フローチャートを確認しよう
選択ソートの特徴を抑えた所で、選択ソートをフローチャートで表現をしていきましょう。
選択ソートをフローチャート で表すと上記の画像の様になります。ポイントは、初めに仮の最小値を定義をしている点です。内側のループでは線形探索して配列の値にアクセスをしていきますが、その際に最小値を更新をしていき、最終的に本当の最小値と仮の最小値を入れ替えます。
コードに置き換えよう
フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。
| 変数 | 概要 |
|---|---|
| array | 配列 |
| i | 配列の添字&ループ回数 |
| j | 配列の添字&ループ回数 |
| temp | 仮置き箱 |
| min | リアルタイムの配列の最小値 |
| k | リアルタイムの配列の最小値の添字 |
def selection_sort(array)
i = 0
while i < array.length
min = array[i]
k = i
j = i+1
while j < array.length
if min > array[j]
min = array[j]
k = j
end
j+=1
end
temp= array[i]
array[i] = array[k]
array[k] = temp
i+=1
end
array
end
array =[2,3,45,5,1,3,5,21,12,23]
selection_sort(array)
p array
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]
それでは、解説していきます。
i = 0まずは、変数iを初期化して、ループ処理を行う準備をします。
while i < array.length
min = array[i]
k = i
j = i+1
endその後、while文を用いて、外側のループ処理を定義をします。なお、指定した条件は、iが配列arrayの要素の数より小さい限り繰り返すという内容になります。まあ、ここまでは、バブルソートと同じです。
min = array[i]こちらは、仮の最小値を定義をしています。外側のループ処理が始まる段階で仮の最小値を定義をしておく事で、内部のループ処理内で配列操作を行いやすくしております。
k = iこちらは、仮の最小値の添字を格納しています。
j = i+1変数jにi+1を格納をしています。選択ソートの特徴として、初期化する段階で配列の最初の要素を最小値として仮定します（最小値を条件として選択した場合）。なので一番初めの要素は、ソート済みと仮定して内側のループ処理を構築をしていきます。したがって、i+1として、最小値と仮定した次の要素からループ処理を組みます。
while j < array.length
if min > array[j]
min = array[j]
k = j
end
j+=1
end内側のループ処理を定義をしていきます。まあ、指定する条件は、外側のループ処理と変わりません。jが配列arrayの要素の数より小さい限り繰り返すという内容になります。
if min > array[j]
min = array[j]
k = j
endこちらのソースコードで最小値を更新をしていきます。最小値とは、一番小さい数を指します。なので、変数minに格納されている値は、リアルタイムで一番小さい数でなければいけません。したがって常にmin <array[j]という関係でなければいけません。この事を踏まえ矛盾を無くせば良いだけですので、最終的に
min > array[j]という場合のみに最小値を更新するという条件を提示すれば常に変数minは、最小値である事を証明できます。
min = array[j]
k = jなお、中身の処理は、上記の通りです。(最小値を更新をしているだけ)
j+=1内側のループ処理の最後で、変数jの値を更新します。
temp= array[i]
array[i] = array[k]
array[k] = temp
i+=1内側のループを抜けたら、仮の最小値と本当の最小値を入れ替えます。ソースコード自体は、バブルソートとほぼ同じなので解説は省略させていただきます。
以上で、選択ソートの解説は終了になります。選択ソートは、バブルソートと比較すると少し複雑になったと思いますが、
- 最小値
- 最大値
が頭の中に入っていれば、さほど難しくは無いと思います。
挿入ソート
挿入ソートとは、整列してある配列に追加要素を適切な場所に挿入する整列アルゴリズムです。要するに挿入済みの要素と挿入する要素を比較して
- 大きいか？
- 小さいか？
という条件で並び替えていきます。文字だけの解説では理解できないと思うので、下記の動画を参照してください。
フローチャートを確認しよう
挿入ソートの特徴を抑えた所で、挿入ソートをフローチャートで表現をしていきましょう。
挿入ソートをフローチャート で表すと上記の画像の様になります。ポイントは、配列の初めの要素を挿入済みと仮定している点です。
コードに置き換えよう
フローチャート を確認をした所で、実際にソースコードに置き換えていきましょう。
| 変数 | 概要 |
|---|---|
| array | 配列 |
| i | 配列の添字&ループ回数 |
| j | 配列の添字&ループ回数 |
| iv | 挿入する値 |
def insertion_sort(array)
i = 1
while i < array.length
iv = array[i]
j = i-1
while j >= 0
if array[j] > iv
array[j+1] = array[j]
else
break
end
j-=1
end
array[j+1] = iv
i+=1
end
array
end
array =[2,3,45,5,1,3,5,21,12,23]
insertion_sort([1,3,4,2,6,5])
#ソート前:[2, 3, 45, 5, 1, 3, 5, 21, 12, 23]
#ソート後:[1, 2, 3, 3, 5, 5, 12, 21, 23, 45]それでは、解説していきます。
i = 1まず初めに変数iを初期化して、ループ処理を行う準備をします。なお、0では無く1を格納しているのは、配列の初めの要素を挿入済みと仮定しているからです。
while i < array.length
iv = array[i]
j = i-1
endその後、while文を用いて、外側のループ処理を定義をします。なお、指定した条件は、iが配列arrayの要素の数より小さい限り繰り返すという内容になります。
iv = array[i]変数ivに挿入する値を格納しています。
j = i-1内側のループ処理に必要な変数j を定義をしておきます。今回は、挿入する要素を基準に左側の要素は挿入済み、右側の要素は挿入が完了していないと仮定してロジックを組んでいます。また、挿入ソートの特徴として、挿入する要素が、指定した条件の関係になるまで要素を入れ替えていきます。したがって、挿入済の要素内で配列操作(バブルソート)を行えば良いですので、（挿入する値の添字）-1という関係が成り立ちます。
なお、今回の挿入ソートは、一番小さい数から順に並ぶ様に実装しています。したがって、バブルソート・選択ソートとは、逆にループ処理を組んでいきます。右から左に処理が繰り返されていくイメージです。
while j >= 0
end先ほどの解説の通り、今回の挿入ソートは、右から左に処理が繰り返されていく様に実装しました。この一連の処理を実現をするためには、while文の条件式に変数jが0より大きい限り繰り返すという条件を提示をします。
if array[j] > iv
array[j+1] = array[j]
else
break
end続いて、今回の肝である条件分岐について解説していきます。
if array[j] > iv
array[j+1] = array[j]
elseこちらのソースコードは、挿入する要素より挿入済の要素が大きかった場合と条件を提示をしています。なお、条件に該当した場合は、挿入済(j)の要素を右にずらします。この作業を行う事で、配列内に空洞ができて、挿入する要素を挿入する事ができます。
else
break
end条件に該当しないすなわち、挿入する要素が挿入済の要素より大きかった場合、つまり、一番小さい数から順に並んでいたらbreak文を用いて、ループ処理を抜けます。
j-=1こちらの記述も忘れずに書いておいてください。無限ループになってしまうので。
array[j+1] = iv
i+=1最終的に、内側のループ処理を抜けたタイミングで、挿入する要素を挿入します。一見、同じ所に挿入していると感じると思いますが、重複せずに問題無く挿入する事ができています。
j-=1内側のループ処理の末尾で変数jに1を引いているため、必ず値が重複しない様になっております。しかし、勘の良い方だったら、下記の様な疑問を持つと思います。
「じゃあ、内側の処理の１回目のループでbreck文が呼び出されて、jの値が一度も更新されない場合ってどうなるの？」
上記の様な疑問を持たれた方は、かなり勘が鋭い方だと思いますが、クリアに考えてみてください。結論から申し上げると、挿入する要素は位置が変わらず挿入済になります。jを初期化した事を思い出してください。
j = i-1
arry[j+1]
i-1+1 i-1つまり、挿入済の要素の最後の位置を指します。そして、arry[j+1]は、挿入する要素の位置の事を指します。なので、jの値が一度も変わらずにループ処理が終わったとしても、挿入する要素は位置が変わらず挿入済になります。逆に考えれば、jの値が更新されると（-1）、処理が左にずれて、挿入する要素が適切な位置に挿入できるまで、jの値を更新し、繰り返すという事になります。
以上で、挿入ソートの解説を終了します。挿入ソートは、選択ソートと比べ、記述量は少なかったです。しかし、省略されている部分も多く、頭の中でループ処理を想像ができないと「ん？」となって根本的には、理解ができないと思います。なので、ループ処理をたくさん書いて覚えていきましょう!!
まとめ：アルゴリズム２
今回は、基本的なソートについて解説していきました。
今回、解説したソートは、基本的な部分なので、繰り返しコードを書いて覚えていきましょう。また、ループ処理についても、ご自身で何かオリジナルのプログラムを組んで、慣れていきましょう！！
もし、ご自身でプログラムを組むのに慣れていない場合は、こちらの記事をを参照してみてください。
どの記事も、How to でプログラムを組んでいくので、時間があればご活用ください。
以上、kazutoでした。