Assyのリベラル文学研究所もご覧ください。

アルゴリズムとデータ構造

探索アルゴリズム

線形探索

データを先頭から順番に探索していく。
探索するデータは先頭にあることも末尾にあることもあるが、平均すると大体真ん中ぐらいで見つかる。

2分探索

データをあらかじめ整列させておき、最初に真ん中と比較し、
二つのデータの関係から前後のどちらかに目的のデータがあることを予測し、その真ん中のデータを比較する。

ハッシュ表探索

ハッシュ関数を利用し、データからハッシュ値を求めて探索する。

整列アルゴリズム

バブルソート

隣り合う要素を比較して、大小が逆であればその要素を入れ替える操作を繰り返す。

挿入ソート

整列された列に、新たな要素を一つずつ適切な位置に挿入する操作を繰り返す。

選択ソート

未整列の部分から最大値(または最小値)を検索し、それを繰り返す。

クイックソート

最初に中間的な基準値を定めて、それよりも大きな値を集めた部分列と小さな値を集めた部分列を振り分ける。
それぞれの部分列の中で基準値を決めて、同様の操作を繰り返す。

シェルソート

ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列させ、
さらに間隔を狭めて同様の操作を繰り返し、最後に間隔を1にして完全に整列させる。

ヒープソート

未整列部分でヒープを構成し、その根から最大値(または最小値)を取り出して整列済の列に移すという操作を繰り返す。

マージソート

未整列のデータ列を前半と後半に分ける分割操作を、これ以上分割できない、大きさが1の列になるところまで繰り返す。
その後、分割した前半と後半をマージ(併合)して、整列済のデータ列を作成することを繰り返し、最終的に全体をマージする。

データ構造

配列

データ構造を連続させたもの。

スタック

後入れ先出し(LIFO)のデータ構造。
データを取り出す時には、最後に入れたものが取り出される。
スタックにデータを入れる操作をpush、データを取り出す操作をpopという。

キュー(待ち行列

先入れ先出しFIFO)のデータ構造。
データを取り出す時には、最初に入れたものが取り出される。
キューにデータを入れる操作をenqueue、データを取り出す操作をdequeueという。

リスト

順序づけられたデータの並び。
データそのものを格納するデータ部と、次・前のデータへのポインタなどを格納するポインタ部に分けて管理する。
次のデータへのポインタのみを持つ「単方向リスト」と前へのポインタと次へのポインタを持つ「双方向リスト」がある。

ハッシュ

あるデータに対してそのデータを代表する値に変換する関数。

木の構造をしたデータ構造。
ノード間の関連は親子関係で表され、根ノード以外の子ノードでは、親ノードは必ずひとつ。
親ノードに対する子ノードの数が二つまでに限定されるものを2分木、三つ以上持てるものを多分木と呼ぶ。

ヒープ

完全2分木の一種で、最大値または最小値を求めるのに適したデータ構造。
「子要素が常に親要素より大きいか等しい」か、「子要素が常に親要素より小さいか等しい」のどちらかになる。

参考文献

徹底攻略 応用情報技術者教科書 平成30年度」を参考に執筆しました。