※このページではアフィリエイト広告を利用しています

【基本情報】基本情報に出てくる代表的なアルゴリズム一覧

基本情報技術者試験

ここでは、「基本情報」における整列・併合・探索、再帰、グラフ、文字列処理、ファイル処理のアルゴリズムに関する代表的なアルゴリズムについて解説しています。

この記事の対象

  • 「基本情報」に出てくるアルゴリズムを知りたい方
  • 基本的なアルゴリズムについて知りたい方
  • 体系的にアルゴリズムを勉強したい方
スポンサーリンク
スポンサーリンク

整列・併合・探索アルゴリズム

項目内容
選択ソート最小値の要素を探し、配列の先頭と入れ替えて並べ替えるもの。
バブルソート配列の端から順番に隣接する要素同士を比較・交換して並べ替えるもの。
マージソート配列を細かく分割して整列しながら並べ替えるもの。
挿入ソート配列から要素を1つずつ取り出し「整列済み配列」の適切な位置に挿入して並べ替えるもの。
シェルソート配列から一定間隔おきに取り出した要素内でソートを繰り返して並べ替えるもの。
クイックソート「基準値を基に配列を分割して整列」を繰り返して並べ替えるもの。
ヒープソート「配列の要素を「順序木」構造にして最大値or最小値を取り出して整列」を繰り返して並べ替えるもの。
線形探索法配列の端から目的の要素を1つずつTrue/Falseで判定して全て探索する方法。
2分探索法「昇順」または「降順」に並んでいる配列を2分割して目的の要素を探索する方法。
ハッシュ表探索法予め定義した要素のキーを基に目的の要素を探索する方法。

再帰的アルゴリズム

再帰(recursion)アルゴリズムとは、自分自身の中から自身を呼び出すことで複雑なアルゴリズムを用いたプログラムを明快に記述できるものです。

具体的なプログラムがあります。気になる方は以下をご参照下さい。

>>>Pythonと関数-再帰の取り扱い方法-

グラフのアルゴリズム

項目内容
深さ優先探索それ以上先に進めない行き止まりのノードに出くわすまで経路を戻らずに隣接ノードを進んでいくもの。
幅優先探索探索を開始する頂点から近い順に探索するもの。
最短経路探索2つのノード間を結ぶ経路の中で、重みが最小の経路を求めるもの。

文字列処理のアルゴリズム

項目内容
文字列照合配列から任意の文字列をマッチさせること。代表的なものとしてボイヤー・ムーア(Boyer-Moore)法がある。
ボイヤー・ムーア法文字列を探索する際、予め「進める値」を定義しておくことで照合を進めるアルゴリズム。

ファイル処理のアルゴリズム

項目内容
併合処理二つの整列済みのレコードで構成されるファイルを、一つの整列されたレコードのファイルにする処理。
コントロールブレーク処理同じキー値を持つレコード群の切れ目で処理を終了して、複数のレコード群の処理を反復する処理。
編集処理既存のファイルのデータを修正する処理。

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