初級者向け アルゴリズムを解説（2）

初級者向け　アルゴリズムを解説

　これからアルゴリズムについて解説をしていきますが、こちらの解説はプログラミング初級者（「最近プログラミングを始めました！！」向けになります。また数回のシリーズに分けてプログラミングで使用されるアルゴリズムを解説していきます。なお、Rubyを使用してコーディングしています。
※このシリーズは「アルゴリズムを、はじめよう（著：伊藤静香）」を参考にしております。
シリーズ(１)： 初級者向け　アルゴリズムを解説（１）はこちら

定番アルゴリズム

　それでは前回の続きから始めましょう。前回、アルゴリズムは「問題や課題を解決するための手順を表現した考え方やアイディア」とお伝えしましたが、アルゴリズムを大きく分けると、探索・整列・数値計算・文字列検索の4つの種類があります。
　そしてその種類ごとに基本的な処理手順を持っているアルゴリズムがあり、それらが定番アルゴリズムとなります。アルゴリズムの各種類の定番アルゴリズムは次の通りです。（一部抜粋）

• 探索
  • 線形探索法
  • 二分探索法
  • ハッシュ探索法
• 整列
  • 単純選択法
  • 単純交換法
  • 単純挿入法
  • クイックソート
• 数値計算
  • エラトステネスのふるい
    
  • ユークリッドの互除法
  • ガウスの消去法
• 文字列探索
  
  • 力まかせの検索法
  • KMP法
  • BM法

　今回は探索の線形探索法を説明します。なお、探索アルゴリズムは目的のデータを探し出すアルゴリズムで検索エンジンに使用されているアルゴリズムになります。

線形探索法(リニアサーチ)

　線形探索法とは、先頭から順番に調べて探す探索アルゴリズムです。まずはイメージを掴んでいただきたいと思いますので、まず３つの枠に区切られた箱をイメージしてください。その各枠には数字が1つずつ入っていて、その数字は箱から出して見なければわからないようになっています。今回はその箱から1つの数字を探して見たいと思います。今回用意した箱と数字は次の通りです。
　[0, 4, 1]　（箱が3つの枠に仕切られ、中には0と4と1が見えないように入っているイメージです。）

　そして、今回は4の数字を探したいと思います。手順は次の通りです。
　1. 先頭の枠を確認
　2. 入っている数字は0（探したい数字と一致しない）
　3. 次の枠に移動
　4. 次の枠を確認
　5. 入っている数字は4(探したい数字と一致した)
　6. 探索終了
　
　それではこれらの内容をコードにしていきましょう。
　なお、線形探索法は反復構造（同じ処理を繰り返す）になっているため、必ず反復する処理を終了させる条件を付加してください。（万が一、探したい数字が箱の中にない場合、プログラムを終了させることができなくなります。）

Ruby

array = [0, 4, 1]    # ①サンプルとして適当な配列を準備
research_number = 4  # ②探索する数字を4を代入
i = 0                # ③要素番号0(先頭)から順に検索

loop {
  if i > array.length - 1 # ④反復する処理を終了させる条件
    puts "探している数字はこの配列に存在しません。"
    break  # loopから抜け出す処理(探索終了)
  elsif array[i] == request_number  # ⑤探したい数値を確認する処理
    puts "要素番号#{i}に4があります。"
    break  # loopから抜け出す処理(探索終了)
  end
  i += 1  # ⑥次の枠を探索するために要素番号に1を加える処理（⑤で探したい数字が一致しなかった場合）
}

解説（丸付きの番号は上記コードのコメントに該当）
　①　3つの数字が入った配列(箱)を用意しました。今回はこの配列に入っている数字を探索しています。
　②　今回は4を探索したいので、変数(research_number)に4を代入しています。
　③　線形探索法では先頭から順番に探索するため、配列の先頭となる要素番号0をiへ代入しています。
　--ここまでが、線形探索法の下準備、以下が実際のアルゴリズムになります。---
　④　これは反復処理を終了させる条件になっています。
　　.lengthメソッドを使用することで配列の要素数(array.length)を調べ、そこから1を引くことで配列の最後の要素番号を取得しています。
　　つまり、iが探索可能な要素番号に収まっているかを確認し、もしiが探索可能な要素番号に収まっていないのであれば探索を強制的に終了させています。
　　もし、この配列に探したい数字が存在せず、また④の処理がない場合、永遠にiは増え続け、プログラムは終了しません。
　⑤　実際に配列から取り出した数字と探したい数字を確認している処理になります。もし、ここで数字が一致した場合、breakによりプログラムは終了します。
　⑥　⑤で数字が一致しなかった場合の処理になります。配列の次の要素を探索するためにiへ1を足しています。
　　なお、⑥の処理が終了したあとは④へ戻り、iが配列の要素数を超える、または一致する数字を探す出すまで④から⑥の処理が繰り返し行われます。

次回予告

　今回はここで終了です。
　次回は探索アルゴリズムの二分探索法について説明していきたいと思います。

　（説明の内容がわかりやすくなるように、徐々に説明方法を修正していきます。）