定番アルゴリズムについて

アルゴリズム

アルゴリズムの考え方は色々とあるが、ここではまず一番基本的な処理手順を持つ「定番アルゴリズム」について書いてみる。

スポンサーリンク

定番アルゴリズムとは何か

定番アルゴリズムとは何か、まず基本的なことは

アルゴリズムは、大きく分けると、探索、整列、数値計算、文字列探索の4つの種類があります。そして、その種類ごとに、基本的な処理手順を持っているアルゴリズムがあり、それらが定番アルゴリズムとされています。

アルゴリズムを、はじめよう 伊藤静香 引用88ページ

・・となっている。

今まで様々なアルゴリズムが生まれ、淘汰されてきた長い歴史の中で今も良いものとして多くのプログラムで使われ続けてきたものであり、またこれを覚えておくと良いプログラムが作れるだろう、というものである。

アルゴリズムの種類

では、定番アルゴリズムの中には更にどんな種類があるのか見ていく。

探索アルゴリズム
  • 線形探索法(リニアサーチ)・・先頭から順番に探す
  • 二分探索法(バイナリサーチ)・・範囲を半分に絞りながら探す
  • ハッシュ探索法・・計算して格納位置を探す
整列
  • 単純選択法(選択ソート)・・最小(大)値を選択して先頭から並び替える
  • 単純交換法(バブルソート)・・隣り合うデータを交換しながら並べる
  • 単純挿入法(挿入ソート)・・データを正しい位置に挿入しながら並べる
  • クイックソート・・基準のデータをもとに大小に分割を繰り返しながら並べ替える
  • マージソート・・二分割とマージ(併合)を利用して並べ替える
  • ヒープソート・・ヒープというデータ構造を利用して並べ替える
  • シェルソート・・グループ分けしながら並べ替える
数値計算
  • エラトステネスのふるい・・素数を求めるアルゴリズム
  • ユークリッドの互除法・・最大公約数を求めるアルゴリズム
  • ガウスの消去法(掃き出し法)・・連立一次方程式を解くアルゴリズム
  • 台形公式(台形測)・・定積分の近似値を求めるアルゴリズム
  • ダイクストラ法・・グラフで最適経路を求めるアルゴリズム
  • 二分法・・方程式を解くアルゴリズム
  • ニュートン法(ニュートン・ラフソン法)・・方程式を解くアルゴリズム
文字列探索
  • 力任せの探索法・・先頭から一文字ずつずらしながら探す
  • KMP(クヌース・モリス・プラット法)・・不一致箇所に着目して探す
  • BM(ボイヤー・ムーア法)・・部分文字列の末尾から探す

・・・と、世の中にはまだまだ数多くのアルゴリズムが存在するが、今回は一般的によく使われるアルゴリズムについて書きだしてみた。

今後、この中から青文字で示したアルゴリズムについての説明をしていく。

タイトルとURLをコピーしました