独学で資格は取れる

資格を独学で勉強してみた記録です。

【応用情報・高度共通】1章 基礎理論 1.4基本アルゴリズム

応用情報・高度共通上部画像

目次

この文章は以下の本を参考にしています。


 

 

1.整列

整列の基本三法

  • ①選択法
  • ②交換法(バブルソート)
  • ③挿入法

 

①選択法

  • まず一番左のデータを他の全部と比較し、最小のデータを左端に置く
  • その一番左のデータ以外について、一番左のデータを他の全部のデータと比較していく
  • これを繰り返していく
  • 比較回数はnの2乗になる

②交換法(バブルソート)

  • 隣同士のデータを比較して並べ替えていく
  • 隣り合う要素の大小関係が逆なら交換するという操作を繰り返す
  • データの比較回数、求め方は選択法と同じ
  • 比較回数はnの2乗になる

 

③挿入法

  • 左から2番目のデータを基準にそれより左のデータを整列した状態になるように適切な位置に挿入する
  • 整列済みの要素の中の適切な位置に新たな要素を挿入する操作を繰り返す
  • 比較回数は①②と異なるが計算量は①②と同じ

 

④クイックソート(交換法の改良版)

  • 小さいデータのグループと大きいデータのグループに分けることを再帰的に繰り返す

 

⑤ヒープソート(選択法の改良版)

  • ヒープと呼ばれる2分木を利用する

 

⑥シェルソート(挿入法の改良版)

  • 整列対象から一定間隔ごとに取りだした要素を整列するという操作を間隔を狭めながら繰り返す

 

⑦マージソート

  • データを分けて、それを併合することで全体を整列させる

 

2.探索

 ①線形探索(逐次探索)

  • データ列の先頭から順に探す

 

②2分探索(バイナリサーチ)

  • 2つに分けながら探索範囲を狭めていく

 

③ハッシュ法による探索

  • ハッシュ値をもとにデータの格納位置を決める方法 

 

参考文献: iTEC社 「2019応用情報・高度共通 午前試験対策書」

 

ブログランキングに参加しております。
よろしければポチっとお願いします!

にほんブログ村 資格ブログへにほんブログ村

資格受験ランキング

プライバシーポリシー